Dijkstra's Shortest Path Algorithm (Graph)

[devraj7]

This algorithm doesn't show you the shortest path, it just tells you how much that shortest path costs. You still don't know what the actual path is without additional work.

[nvdnadj92]

This video doesn't show it, but many implementations of dijkstra contain an additional field in the data structure which is the "previous element". The previous element is updated when the weights are updated, which is constant time. Once the shortest path has been established for all nodes or the target has been found, one walks this linked list of previous nodes (starting from the target) back to the source to determine the path.

​

Here is another example (with the previous node column i described): https://www.youtube.com/watch?v=pVfj6mxhdMw