# Dijkstra’s algorithm

Dijkstra's algorithm is way of finding shortest path from a source vertex to sink in a given connected and weighted graph. It is somewhat similar to Prim's algorithm and it works for directed as well as undirected graphs. The step by step process is specified below :

1. Source vertex is chosen and marked.
2. Mark distances at all vertices as infinity and at source vertex as 0.
3. Update the distances of adjacent vertices from infinity by given distances on the graph .
4. We look for minimum distance value from source vertex to adjacent vertices.
5. The minimum distance is chosen and next vertex is marked.
6. Look for the adjacent vertices of marked vertex.
7. Replace the distance if it is less than the mentioned value at the vertices.
8. Keep on following the same procedure until shortest path to sink is obtained.

Example:

Consider a weighted and undirected graph as shown in Fig 1

• Choose a source vertex.In Fig 2 ,a is chosen as the source vertex.
• Mark all the distances at vertices as infinity initially and distance of source vertex as 0

• Look for neighbors of source vertex a.(Fig 3).
• b and i are the adjacent vertices.
• Update the distance at b from infinity to 4 and at i to 8.
• Find the minimum distance from a.
• 4 is smaller than 8 so b is the next marked vertex.

• Look for the neighbors of b.
• c and i are the adjacent vertices.
• Update value at c from infinity to 12(4+8) as distance from source to c is 12.(Fig 4)
• Distance from a to i through b is 15(11+4)  and a to i directly is 8.So 8 is not updated.
• Look for next min distance  to a vertex and do not count already marked vertices and edges.
• The distance at c is 12 and at i is 8,so i  is marked.

• Look for neighbors of i .
• Update distance at h to 15(8+7) and at g to 9.
• Distance from source a to b is 4 and a to b through i is 19 so it is not updated.
• Look for next minimum distance from marked vertices.
• 12,15,9 are the respective distances from marked vertices.
• Mark vertex g and Edge(i,g) as 9 is the minimum distance from source a to g through i.

• Look for neighbors of g.
• The distance at h from a through i  is 15 and from a through  i and g is again 15 so it is not updated(Fig 6).
• The distance from a to f through i and g is 11.So update it by 11.
• Look for the next minimum distance(Fig 7).
• 12,15,11 are the distances from marked vertices.
• Mark f and Edge(g,f) as distance is minimum.
• Neighbors of f are c,d,e.
• Distance at c is not required to be updated.
• Update distance at d to 25(11+14) and at e to 21(11+10)(Fig 8).
• Look for minimum distance.
• 12,15,19,21 are the distances available for consideration.
• Mark vertex c as 12 is minimum.

• Distance of neighbors of c is not required to be updated.
• Mark d and then e.(Fig 9)

The following table gives the details of dijkstra's algorithm applied on Fig 1.The shortest path from a to e is {a,b,i,g,f,c,d,e} with minimum cost of 21.

Rate this post