Dijkstra shortest Path Algorithm : Procedure, Code, Uses

In the previous article, we learned about Graph representation and Graph traversal in Data Structures, In this article, we will learn about Dijkstra shortest Path Algorithm in Data Structures.

50

Dijkstra algorithm is utilized to find the shortest path between the nodes in a graph. For example, in any road network, if a person wants to go from one station to another, needs to know the shortest path between the two stations. The station can be represented as the node and the routes can be represented as the edges.

The procedure of the Dijkstra algorithm

• Maintain a list of unvisited nodes.
• Choose a node ( the source), mark it as permanent, and assign a maximum possible cost(i.e., infinity) to every other node.
• The cost of the source is zero as it actually takes nothing to reach from the source node to itself.
• In every subsequent step, minimize the cost for each node. The cost can be any type of feasibility cost. For example, the distance or time is taken to reach that node from the source node. To minimize the cost, calculate the new cost for each unvisited neighboring node from the current node.
• When all neighbors of the current node are considered, mark the temporary node with the least cost as the permanent node.
• Select a node from the list of unvisited nodes having the smallest code, take it as a working node, and repeat steps 4 and 5 until the destination node becomes a parent.

Implementation of Dijkstra Algorithm

Now, we will see the implementation of this algorithm using code –

#include<stdio.h>

#include<conio.h>

#define INFINITY 9999

#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode);

int main()

{

int G[MAX][MAX],i,j,n,u;

printf("Enter no. of vertices:");

scanf("%d",&n);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

scanf("%d",&G[i][j]);

printf("\nEnter the starting node:");

scanf("%d",&u);

dijkstra(G,n,u);

return 0;

}

void dijkstra(int G[MAX][MAX],int n,int startnode)

{

int cost[MAX][MAX],distance[MAX],pred[MAX];

int visited[MAX],count,mindistance,nextnode,i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(G[i][j]==0)

cost[i][j]=INFINITY;

else

cost[i][j]=G[i][j];

for(i=0;i<n;i++)

{

distance[i]=cost[startnode][i];

pred[i]=startnode;

visited[i]=0;

}

distance[startnode]=0;

visited[startnode]=1;

count=1;

while(count<n-1)

{

mindistance=INFINITY;

for(i=0;i<n;i++)

if(distance[i]<mindistance&&!visited[i])

{

mindistance=distance[i];

nextnode=i;

}

visited[nextnode]=1;

for(i=0;i<n;i++)

if(!visited[i])

if(mindistance+cost[nextnode][i]<distance[i])

{

distance[i]=mindistance+cost[nextnode][i];

pred[i]=nextnode;

}

count++;

}

for(i=0;i<n;i++)

if(i!=startnode)

{

printf("\nDistance of node%d=%d",i,distance[i]);

printf("\nPath=%d",i);

j=i;

do

{

j=pred[j];

printf("<-%d",j);

}while(j!=startnode);

}

}

Uses of Dijkstra Algorithm in Data Structures

This algorithm is also widely used in real life since it has a lot of real-world applications –

• It is used in finding Shortest Path.
• It is used in geographical Maps.
• To find locations of Map which refers to vertices of the graph.
• Distance between the location refers to edges.
• It is used in IP routing to find the Open Shortest Path First.
• It is used in the telephone network.
• It’s also called the A* algorithm.

This site uses Akismet to reduce spam. Learn how your comment data is processed.