Dijkstra’s Algorithm Example Step by Step

Dijkstra’s Algorithm is a greedy algorithm for solving the single-source, shortest-path problem on an edge-weighted graph in which all the weights are non-negative. It finds the shortest paths from some initial vertex, say s, to all the other vertices one by one. The essential features of Dijkstra’s Algorithm are the order in which the paths are determined: The paths are discovered in the order of their weighted lengths, starting with the shortest, and proceeding to the longest.

Dijkstra’s Algorithm keeps two sets of vertices:
i. U vertices whose shortest paths have already been determined
ii. V-U remainder vertices.

Algorithm:
[c]
Algorithm fnDijkstra (s, d, n)
{
for(i=1; i<=n; i++) { dist[i]=" "; pred[i]=NULL; status[i]=Temporary; } status[s]=Permanent; dist[s]=0; current=s; while(current!=d) { dc=dist[current]; for(all vertices i, that are adjacent of current and status[i]=Temporary) { newdist=dc+W[current][i]; if(newdist< dist[i]) { dist[i] = newdist; pred[i] = current; } } Choose node k such that status[k] = Temporary and dist[k] is smallest; current = k; status[k]= Permanent; } } // End of Algorithm [/c]