The Dijkstra algorithm is able to solve the problem of finding the shortest path from the source s to all of the nodes. The algorithm maintains a label d(i) to the nodes representing an upper bound on the length of the shortest path of the node i.
At each step, the algorithm partitions the nodes in V into two sets: the set of permanently labeled nodes and the set of nodes that are still temporarily labeled. The distance of permanently labeled nodes represents the shortest path distance from the source to these nodes, whereas the temporary labels contain a value that can be greater than or equal to the shortest path length.
The basic idea of the algorithm is to start from the source and try to permanently label the successor ...
