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’

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

• Quick Sort
• Bubble Sort
• Merge Sort
• Insertion Sort
• Selection Sort
• Heap Sort
• Radix Sort
• Bucket Sort

Additional Reading

• SEO Practices Everyone Should Follow SEO Rules
• Complete Top SEO Checklist
• Yoast Seo Premium 15.2 Nulled – WordPress SEO Plugin
• Top 50+ SEO Interview Questions
• What is a Backlink? How to Get More Backlinks

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 !