## Dijkstra's Algorithm (Shortest Path)

###

Consider a directed graph G = (V, E).

**Problem **Determine the length of the shortest path from the source to
each of the other nodes of the graph. This problem can be solved by a greedy
algorithm often called Dijkstra's algorithm.

The algorithm maintains two sets of vertices, S and C. At every stage the set
S contains those vertices that have already been selected and set C contains all
the other vertices.
Hence we have the invariant property V=S U C.
When algorithm starts Delta contains only the source vertex and when the
algorithm halts, Delta contains all the vertices of the graph and problem is
solved.
At each step algorithm choose the vertex in C whose distance to the source is
least and add it to S.