Dijkstra’s Algorithm shortest path with example

There are different algorithm to find shortest path between two vertices in a weight graph. we discuss here Dijkstra’s algorithm for shortest path. Consider a weighted graph G . The length of a path in a weighted graph is the sum of the weights of the edges of this path And the shortest path between the two vertices is the minimum length of the path.

A weighted graph is a graph G, in which each edge is assigned a non-negative real number, w(e), called the weight of e. The weight of subgraph H of G is the sum of the weight of the edge is of the subgraph H.

Dijkstra’s Algorithm for shortest path

• step1: Label the initial vertex of the graph with weight zero.
• step2: Calculate the weight of all vertices  adjacent to the initial vertex corresponding to the weight of the edges  incident on the initial vertex.
• step3: Level these vertices with a smallest possible value of their weights.
• step4: Calculate the weight of all those vertices which are adjacent to the vertices with minimum weights determined in step3.
• step5: label these vertices with minimum weight.
• step6: continue this process until all the vertices of weighted graph are labeled.
• step7: Trace the part of cumulative minimum weight from the initial vertex to desire vertex.

Pseudo code for Dijkstra’s algorithm

{
for i=1 to n
L(vi)= infinity(∞)
L(a)=0
S=ø //the labels are now initialized so that all other labels are infinity and S is empty set
while Z ∉ S
begin
U=a vertex not in S with L(u) minimal
S=SU{u}
for all vertices v not in S
If L(u)+w(u,v)<L(v) then L(v)=L(u)+w(u,v)
//this ads a vertex
end //L(z)= length of a shortest path from a to z
}

Example of Dijkstra’s algorithm

Using this algorithm to find shortest path in the graph given below:

First we have to find shortest path from the vertex a to each of other vertices. Let the weight of vertex is zero and weight of all remaining vertices is infinity (∞). i.e

Now, the adjacent vertices of a are b & c, we calculate weight of b & c and the label them with minimum weight.

weight(b) = wt(a)+wt(a,b) =0+6=6

weight(c) = wt(a)+wt(a,c) =0+1=1 since c has minimum weight so, we select it

Now, the adjacent vertices of c are b, e & d, we calculate weight of b, e & d and the label them with minimum weight.

weight(b) = wt(c)+wt(c,b) =1+2=3

weight(e) = wt(c)+wt(c,e) =1+5=6

weight(b) = wt(a)+wt(a,b) =0+6=6 since c has minimum weight so, we select it & replace previous wt of b by new weight.

Now, the adjacent vertices of b are e & d so

weight(e) = wt(b)+wt(b,e) =3+3=6

weight(d) = wt(b)+wt(b,d) =3+1=4 since d has minimum weight so, we select it & replace previous wt of b by new weight.

therefore: the shortest path from a to c is a-c length= 1,

The shortest path from a to b is a-c-b, length=3

The shortest path from a to d is a-c-b-d, length=4

The shortest path from a to e is a-c-e, length=6

Related post