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**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

Vertex | (a) | b | c | d | e | |

Label | 0 | ∞ | ∞ | ∞ |

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

Vertex | a | b | c | d | e | |

Label | 0 | 6 | 1 | ∞ | ∞ |

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.

Vertex | a | b | c | d | e |

Label | 0 | 3 | 1 | 7 | 6 |

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.

Vertex | a | b | c | d | e |

Label | 0 | 3 | 1 | 4 | 6 |

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

**What is Kruskal’s algorithm?**

**Ans:**There are many algorithm for determining the minimal spanning tree of the given weighted graph. Here we discuss Kruskal’s algorithm in data structure…Read more