Home » C++ programming language

# Dijkstra's Algorithm: Explanation and Implementation with C++ program

Learn: What is **Dijkstra's Algorithm**, why it is used and how it will be implemented using a C++ program?

Submitted by Shubham Singh Rajawat, on June 21, 2017

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

Given a graph with the starting vertex.

**Algorithm:**

1. Initially **Dset** contains **src**

dist[s]=0 dist[v]= ∞

2. Set **Dset** to initially empty

3. 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)

**How about we understand this with the help of an example:**

Initially Dset is empty and the distance of all the vertices is set to infinity except the source which is set to zero. First we find the vertex with minimum distance. The vertex ‘A’ got picked as it is the source so update Dset for A.

Now update the distance of its adjacent vertices which B and C. Now find the vertex whose distance is minimum which is C.

So update Dset for C and update the distance of its adjacent vertices. Find the vertex with minimum distance which is B.

Update Dset for B and update distance of its adjacent vertices and then find the vertex with minimum distance which is G.

Update Dset for G and update distance of its adjacent vertices and find the vertex with minimum distance which is E.

Update Dset for E and update distance of its adjacent vertices and find the vertex with minimum distance which is F.

Update Dset for F and update distance of its adjacent vertices and find the vertex with minimum distance which is D.

Update Dset for D.

As all the vertices are part of Dset so we got the shortest path which contains all the vertices. So the graph for shortest path from vertex A is

**Consider the program:**

#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) /*Method to implement shortest path algorithm*/ { int dist[vertex]; bool Dset[vertex]; for(int i=0;i<vertex;i++) /*Initialize distance of all the vertex to INFINITY and Dset as false*/ { dist[i]=INT_MAX; Dset[i]=false; } dist[src]=0; /*Initialize the distance of the source vertec to zero*/ for(int c=0;c<vertex;c++) { int u=minimumDist(dist,Dset); /*u is any vertex that is not yet included in Dset and has minimum distance*/ Dset[u]=true; /*If the vertex with minimum distance found include it to Dset*/ for(int v=0;v<vertex;v++) /*Update dist[v] if not in Dset and their is a path from src to v through u that has distance minimum than current value of dist[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++) /*will print the vertex with their distance from the source to the console */ { 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions