CREATE OWN LIBRARY

Introduction

The Dijsktra’s algorithm is used for finding the shortest path from a source vertex to all the other vertices, in a weighted graph. It is a solution to the single-source shortest path problem. It was published in the year 1959 and named after its creator Dutch computer scientist Edsger Dijkstra.

Suppose a cab driver wants to go home after his last passenger drop in the shortest possible way. He knows that some roads are heavily congested and difficult to use. In Dijkstra’s algorithm, this means that the edge has a larger weight, so the algorithm will try to avoid such edges with larger weights. 

Example:

 Let us consider a graph G as shown in Fig 2, which has 4 vertices and 4 directed weighted edges. Let the source vertex be ‘0’.

The computation for finding the shortest distance of each vertex in the graph from its source vertex has been shown in the table below, at each iteration, we find the vertex with the shortest distance from the source vertex and then propagate the changes in the shortest distances for each vertex if a shorter path between the source vertex and selected vertex exists via the visited vertices.

Algorithm:

Input: 

Graph G and the source vertex s.

Output:

The shortest distance between each of the vertices in the graph from the source vertex(i.e. s) .

Algo:

Step 1: Start.

Step 2: Defining the dijkstra(G,s) function

l  Repeat for every vertices v in graph G

(a) Set minHeap < v.

(b) Set dist[v]<=Infinity

l  Set dist[s]<=0.

l  Repeat while minHeap is not empty

(a) Set u<= Root of minHeap.

(b)  Remove u from minHeap and mark it visited.

(c)  Repeat for each p in neighbours of u

If (dist[p]>dist[u]+w[u,p]) then,

Set dist[p]<=dist[u]+weight[u,p].

l  Repeat for every v in graph G

(a)  Display dist[v].

Step 3: Stop.