Dijkstra's algorithm

Image of Author
April 3, 2025 (last updated May 23, 2025)

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

There are nodes. Those nodes are weighted. Start the search from an arbitrary initial node. You can explore all nodes from here, but for this explanation let's stipulate an arbitrary destination node as well. Starting from the initial node, explore connected nodes. Assign values to the nodes corresponding to the least sum path to it. For each next step pick the node with the lowest sum and explore it's connections. Since you are always start with the lowest sum node, you always are exploring the "shortest paths" first, meaning it is guaranteed you find the "shortest path" to the destination node first.

There can be no tricky shortcut paths that the algorithm misses. For example if you had a "trick node" that was heavily weight but afterwards immediately connected to the destination node, Dijkstra's would still search that node eventually. This is because, by definition, longer paths have to eventually exceed the weight of the trick node. If a path did not exceed the weight of the trick node then it is in fact the shortest path.

Djikstra's with all node weights set to 1 is equivalent to a breadth-first search. (I think this has been proven. It's at least intuitively feels true.)