Dijkstra's Algorithm Implementation with C++ program

Dijkstra’s algorithm aka the shortest path algorithm is used to find the shortest path in a graph that covers all the vertices.

Algorithm:

Table of Contents

Initially Dset contains src
dist[s]=0 dist[v]= ∞
Set Dset to initially empty
While all the elements in the graph are not added to ‘Dset’

A. Let ‘u’ be any vertex not in ‘Dset’ and has minimum label dist[u]
B. Add ‘u’ to Dset
C. Update the label of the elements adjacent to u
For each vertex ‘v’ adjacent to u
If ‘v’ is not in ‘Dset’ then
If dist[u]+weight(u,v)<dist[v] then
Dist[v]=dist[u]+weight(u,v)

Dijkstra Algorithm program using C++

#include<iostream>
#include<climits>     /*Used for INT_MAX*/
using namespace std;
#define vertex 7      /*It is the total no of verteices in the graph*/
int minimumDist(int dist[], bool Dset[])   /*A method to find the vertex with minimum distance which is not yet included in Dset*/
{
	int min=INT_MAX,index;                 /*initialize min with the maximum possible value as infinity does not exist */
	for(int v=0;v<vertex;v++)
	{
		if(Dset[v]==false && dist[v]<=min)      
		{
			min=dist[v];
			index=v;
		}
	}
	return index;
}
void dijkstra(int graph[vertex][vertex],int src) 
{
	int dist[vertex];                             
	bool Dset[vertex];
	for(int i=0;i<vertex;i++)                    
	{
		dist[i]=INT_MAX;
		Dset[i]=false;	
	}
	dist[src]=0;                                  
	for(int c=0;c<vertex;c++)                           
	{
		int u=minimumDist(dist,Dset);             
		Dset[u]=true;                              
		for(int v=0;v<vertex;v++)                  
		
		{
			if(!Dset[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u][v]<dist[v])
			dist[v]=dist[u]+graph[u][v];
		}
	}
	cout<<"Vertex\t\tDistance from source"<<endl;
	for(int i=0;i<vertex;i++)                       
	{
		char c=65+i;
		cout<<c<<"\t\t"<<dist[i]<<endl;
	}
}
int main()
{
	int graph[vertex][vertex]={{0,5,3,0,0,0,0},{0,0,2,0,3,0,1},{0,0,0,7,7,0,0},{2,0,0,0,0,6,0},{0,0,0,2,0,1,0},{0,0,0,0,0,0,0},
		                        {0,0,0,0,1,0,0}};
	dijkstra(graph,0);
	return 0;	                        
}

OUTPUT



Vertex      Distance from source
A               0
B               5
C               3
D               9
E               7
F               8
G               6

Types of Sorting Algorithms:

Additional Reading

If you found this post useful, don’t forget to share this with your friends, and if you have any query feel free to comment it in the comment section.
Thank you 😊 Keep Learning !