- Note the distances from a current (initial) node to all neighbouring nodes.
- Mark the current node as visited and move to the next node with the smallest distance and set it as the current node.
- If the destination node is marked visited, stop.
- Otherwise repeat at 1.

- Dijkstra's shortest path algorithm can be used for full traversal (illustrated in the animation) where all the nodes are visited in order to determine all the distances between node and node . However, one can observe in the illustration that when nodes , and are visited, the choice is given between following a path with weight to , a path of weight to and a path of weight to . In the illustration we chose a full traversal, that is, we visit , even though we could have directly selected the shortest path with weight from to .
- One invariant for the full-traversal variant of Dijkstra is that there is a minimal path from a starting node to a destination node if and only if the queue of unvisited nodes is empty at the end.

- Worst case: where is the number of edges and is the number of vertices.

fuss/algorithms/shortest_path/dijkstra.txt ยท Last modified: 2017/02/22 18:30 (external edit)

For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.