But instead of alternating between sides, it appears that advancing on whichever side has visited the fewest nodes yet accelerates the algorithm in a lot of cases.
Would it be even better to advance whichever side’s frontier (the queue) is currently smaller? It seems like the frontier is the part you have to iterate, while the visited set is a hash lookup, so the size of the frontier would matter more.
Having tried both, there doesn’t seem to be any difference in performance. Said otherwise, the performance gain is the same whether you check the count of visited nodes or the size of the queue. I agree however that checking on queue size matches more the explanation I give later in the article, so I’ll change that.
Unfortunately the interactive examples don’t work in Safari on an iPad. I can see the tabs and the slider, but the graph itself isn’t displayed. Once I’m at my Mac I’ll look in the JS console to check for exceptions.
Yep, many people on Reddit and HN have complained about the animations not working on Safari (iOS and Mac). I’ve tested the post on BrowserStack but since the free tier is limited to 1-minute sessions it’s hard to diagnose properly. I’ve already fixed one Safari bug that was caused by WebKit’s NodeList type not having a values() method, so I convert it to an array instead. But there seems to be other bugs related the SVG styling. I’m installing a Sequoia VM right now so I can try and fix the whole post. Safari is the new IE.
I think I would use Dafny for this; I’ve seen it used to prove the termination of BFS so I think it wouldn’t be far-fetched to assume it could be used to prove a similar algorithm gives (or not) a minimal-length path.
I am wondering if there are good large monitors (40 or 50 inches) that can be used as non-smart TVs. Or if the only workaround is to not connect smart TVs to the internet ever.
LG sells a 43” IPS monitor (powered USB-C connection with hub feature etc., but other inputs as well) for ~$500. We use a few of them at work. Could be brighter, could have better colors, but otherwise fine.
There was an Austrian manufacturer called Nogis that offered a nice range of dumb TVs, but they stopped operations a few months ago. They only shipped within Austria.
I think this is an untapped niche in the market, to be honest.
I used to think that too, but this niche is so small as not to matter much. Plus, you can just grab a random “smart” TV and simply never connect it to obtain the same results (that’s what I’ve done at home). Often better, given that existing “smart” TVs generally have high quality displays.
I have a Samsung “smart” TV that I just use as a gaming monitor, I’ve changed the wifi network but never bothered to connect it to it.
However, I do believe there will be a future where if you buy a “smart” TV it will not work unless it has been connected to the internet, at least intermittently. In the grim farnear future, privacy will be a luxury for the rich.
Cheaper than buying a “smart” TV is buying no TV. I don’t have one, nor do I subscribe to Netflix or whatever. If I have time for entertainment, there are public libraries¹ and there is much fiction that people publish free on the Web, some of which is even good.
¹ linked for clarity because it’s far from the usual meaning of “library” here
Basically a 48” LG C1, but without any smart functionality and with HDMI, DP and USB-C-Alt Mode compatibility. I’ve got one, it’s awesome.
Only downside: any framerate change takes 7 seconds to renegotiate. The TV supports VRR, so that wouldn’t be an issue, but my nvidia shield doesn’t support VRR.
I own a 55 inch Bravia TV from around 2016, it’s technically smart, but I use it as a large monitor. It’s good at displaying whatever I throw at it. I don’t connect it to my Wi-Fi.
I have a dedicated Android TV box (Nokia 8000) for casting and Plex, that I can yank or upgrade when I see fit without having to change my TV.
Would it be even better to advance whichever side’s frontier (the queue) is currently smaller? It seems like the frontier is the part you have to iterate, while the visited set is a hash lookup, so the size of the frontier would matter more.
Having tried both, there doesn’t seem to be any difference in performance. Said otherwise, the performance gain is the same whether you check the count of visited nodes or the size of the queue. I agree however that checking on queue size matches more the explanation I give later in the article, so I’ll change that.
Unfortunately the interactive examples don’t work in Safari on an iPad. I can see the tabs and the slider, but the graph itself isn’t displayed. Once I’m at my Mac I’ll look in the JS console to check for exceptions.
Yep, many people on Reddit and HN have complained about the animations not working on Safari (iOS and Mac). I’ve tested the post on BrowserStack but since the free tier is limited to 1-minute sessions it’s hard to diagnose properly. I’ve already fixed one Safari bug that was caused by WebKit’s NodeList type not having a values() method, so I convert it to an array instead. But there seems to be other bugs related the SVG styling. I’m installing a Sequoia VM right now so I can try and fix the whole post. Safari is the new IE.
It’s not; it just isn’t Chrome or Firefox. This is the downside to not having a browser monoculture. Diversity means things won’t be 100% compatible.
Nice post. Saving this for an example of a seemingly correct but actually wrong algorithm to try formally proving correct.
Interesting! What tool/approach would you use for such a formal proof?
I think I would use Dafny for this; I’ve seen it used to prove the termination of BFS so I think it wouldn’t be far-fetched to assume it could be used to prove a similar algorithm gives (or not) a minimal-length path.
I think Dafny would be a good choice as the OP suggests in a sibling comment, but personally I will try to prove it using TLA+’s proof language.
I am wondering if there are good large monitors (40 or 50 inches) that can be used as non-smart TVs. Or if the only workaround is to not connect smart TVs to the internet ever.
LG sells a 43” IPS monitor (powered USB-C connection with hub feature etc., but other inputs as well) for ~$500. We use a few of them at work. Could be brighter, could have better colors, but otherwise fine.
There was an Austrian manufacturer called Nogis that offered a nice range of dumb TVs, but they stopped operations a few months ago. They only shipped within Austria.
I think this is an untapped niche in the market, to be honest.
I used to think that too, but this niche is so small as not to matter much. Plus, you can just grab a random “smart” TV and simply never connect it to obtain the same results (that’s what I’ve done at home). Often better, given that existing “smart” TVs generally have high quality displays.
I have a Samsung “smart” TV that I just use as a gaming monitor, I’ve changed the wifi network but never bothered to connect it to it.
However, I do believe there will be a future where if you buy a “smart” TV it will not work unless it has been connected to the internet, at least intermittently. In the grim
farnear future, privacy will be a luxury for the rich.Cheaper than buying a “smart” TV is buying no TV. I don’t have one, nor do I subscribe to Netflix or whatever. If I have time for entertainment, there are public libraries¹ and there is much fiction that people publish free on the Web, some of which is even good.
¹ linked for clarity because it’s far from the usual meaning of “library” here
This might work for you but perhaps not for the other members of your household.
https://www.gigabyte.com/Monitor/AORUS-FO48U
Basically a 48” LG C1, but without any smart functionality and with HDMI, DP and USB-C-Alt Mode compatibility. I’ve got one, it’s awesome.
Only downside: any framerate change takes 7 seconds to renegotiate. The TV supports VRR, so that wouldn’t be an issue, but my nvidia shield doesn’t support VRR.
I own a 55 inch Bravia TV from around 2016, it’s technically smart, but I use it as a large monitor. It’s good at displaying whatever I throw at it. I don’t connect it to my Wi-Fi.
I have a dedicated Android TV box (Nokia 8000) for casting and Plex, that I can yank or upgrade when I see fit without having to change my TV.