HomePOSTDijkstra's Algorithm Implementation with C++ program

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:

  • 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’

<img width=
  • 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

READ MORE

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 !

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -

Most Popular

- Advertisment -