3 ms·
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 sta
by 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.