# Dijkstra's Shortest Path Algorithm

## Algorithm

1. Note the distances from a current (initial) node to all neighbouring nodes.
2. Mark the current node as visited and move to the next node with the smallest distance and set it as the current node.
3. If the destination node is marked visited, stop.
4. 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.

## Performance

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