I had to revisit Dijkstra's Algorithm in order to solve an Advent of Code problem, and decided to extract the explanation into it's own post here.
There are many resources on YouTube that do a great job explaining the shortest path algorithm. I used the following YouTube videos to remind myself of the algorithm -
https://www.youtube.com/watch?v=pVfj6mxhdMw
https://www.youtube.com/watch?v=pSqmAO-m7Lk
I believe that at the core of most explanations, is the following working table -
At the end of the algorithmic run, it should be populated with all vertices in the problem. The actual implementation details vary but we need to keep track of the shortest distance of each and every node from the starting point. Optionally, we may also need to keep track of the previous vertex that was part of the shortest path. This is useful in determining all the nodes involved in the shortest path
Some other mnemonics that usually aid me in implementation details -
- Heap - This is used to keep track of nodes to be visited
- Specifically, a priority queue that is sorted on distance from start
- Visited - Track nodes that we have already processed
- We can use this to reduce our problem set as we have already determined the best shortest distance from the start for these nodes
- Improve - In each step, improve the shortest distance from start for all neighboring nodes that haven't been visited
- "make the local optimum choices in the hope of finding the global optimum choice"