4 ms·

This title is arguably disingenuous because the original algorithm wasn't Dijkstra's. Dijkstra's algorithm is the algorithm as specified with the runtime chara

This title is arguably disingenuous because the original algorithm wasn't Dijkstra's. Dijkstra's algorithm is the algorithm as specified with the runtime characteristics as specified. He wrote a different algorithm which can solve the same problem and works a lot like Dijkstra's but is much slower. Then he finally actually implemented Dijkstra's and the result was the speedup. The title lead me to believe that he found some way to gain big speedups in Dijkstra's algorithm. This is like me writing an article about prime factorization and doing naive trial division and then making claims like this when I instead choose to use a sieve.

ascar 5y ago
This should be further up. The title is definitely wrong and misleading. "Improving my shortest path algorithm with Dijkstra's algorithm by a factor of 2700!" would be more accurate. The author is an undergraduate student so probably just missed that part about Dijkstra's algorithm, but the title should be changed nonetheless.
mysterydip 5y ago
Same, I was excited to read about it as I'm doing Dijkstra maps for a roguelike and that kind of speedup would be an incredible gain. This does go back to the "why is the web so slow?" question from the other day, though: lots of code can naively solve a problem without being efficient, and a lot of development is done on trivial-sized data quantities for which the difference is not as noticeable.
nottorp 5y ago
Also even ignoring what's Dijkstra's and what isn't, the speedup isn't a constant 2700 factor but it's a reduction in complexity.
gus_massa 5y ago
I used to teach Dijkstra to young students a long time ago. I usually started explaining the "naive" version, because IIRC the priority queue was not in the standard library, or they didn't know how to use it. Going from the obvious backtracking algorithm to the naive Dijkstra algorithm, reduce the complexity from exponential to quadratic, that is a huge difference and is visible even in small boards. Going from quadratic to loglinear is a nice improvement, and it's easier if you have already understood the other part. Perhaps he was taught the naive version and rediscovered the full version. Perhaps he was taught both and should have been more clear about that. I agree that this is not a new groundbreaking discovery, but I think it's a nice post anyway.

ascar 5y ago

This should be further up. The title is definitely wrong and misleading. "Improving my shortest path algorithm with Dijkstra's algorithm by a factor of 2700!" would be more accurate. The author is an undergraduate student so probably just missed that part about Dijkstra's algorithm, but the title should be changed nonetheless.

mysterydip 5y ago

Same, I was excited to read about it as I'm doing Dijkstra maps for a roguelike and that kind of speedup would be an incredible gain. This does go back to the "why is the web so slow?" question from the other day, though: lots of code can naively solve a problem without being efficient, and a lot of development is done on trivial-sized data quantities for which the difference is not as noticeable.

nottorp 5y ago

Also even ignoring what's Dijkstra's and what isn't, the speedup isn't a constant 2700 factor but it's a reduction in complexity.

gus_massa 5y ago

I used to teach Dijkstra to young students a long time ago. I usually started explaining the "naive" version, because IIRC the priority queue was not in the standard library, or they didn't know how to use it. Going from the obvious backtracking algorithm to the naive Dijkstra algorithm, reduce the complexity from exponential to quadratic, that is a huge difference and is visible even in small boards. Going from quadratic to loglinear is a nice improvement, and it's easier if you have already understood the other part. Perhaps he was taught the naive version and rediscovered the full version. Perhaps he was taught both and should have been more clear about that. I agree that this is not a new groundbreaking discovery, but I think it's a nice post anyway.