What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Dijkstra's Algorithm in C++ (Shortest Path Algorithm)

  • May 20, 2021
  • 7 Minutes Read
Dijkstra's Algorithm in C++ (Shortest Path Algorithm)

In this article, we will study what is the graph and what is Dijkstra's algorithm. Further, we will study the example of Dijkstra's algorithm and its c++ code along with its corresponding output. We will also further study the practical application of this algorithm in the real world. So let's get started!

What is Graph?

The graph is a non-linear data structure that involves nodes and edges. The nodes are the vertices and edges are the lines that connect the two nodes in the graph. Therefore, the graph can be defined as a set of vertices and a set of edges that connect the nodes. If we consider Facebook as a graph then the collection of people on Facebook is considered as nodes and the connection between them can be considered as edges.

What is Dijkstra’s Algorithm?

Dijkstra’s algorithm is also known as the shortest path algorithm. It is an algorithm used to find the shortest path between nodes of the graph. The algorithm creates the tree of the shortest paths from the starting source vertex from all other points in the graph. It differs from the minimum spanning tree as the shortest distance between two vertices may not be included in all the vertices of the graph. The algorithm works by building a set of nodes that have a minimum distance from the source. Here, Dijkstra's algorithm uses a greedy approach to solve the problem and find the best solution.

Algorithm for Dijkstra’s in C++

  1. First of all, we will mark all vertex as unvisited vertex
  2. Then, we will mark the source vertex as 0 and all other vertex as infinity
  3. Consider source vertex as current vertex
  4. Calculate the path length of all the neighboring vertex from the current vertex by adding the weight of the edge in the current vertex
  5. Now, if the new path length is smaller than the previous path length then replace it otherwise ignore it
  6. Mark the current vertex as visited after visiting the neighbour vertex of current vertex
  7. Select the vertex with the smallest path length as the new current vertex and go back to step 4.
  8. Repeat this process until all the vertex are marked as visited.

Once we go through the algorithm, we can backtrack the source vertex and find our shortest path.

Pseudocode of Dijkstra’s Algorithm in C++

function dijkstra(G, S)
    for each vertex V in G
        dist[V] <- infinite
        prev[V] <- NULL
        If V != S, add V to Priority Queue Q
    dist[S] <- 0
    
    while Q IS NOT EMPTY
        U <- Extract MIN from Q
        for each unvisited neighbour V of U
            temperoryDist <- dist[U] + edgeWeight(U, V)
            if temperoryDist < dist[V]
                dist[V] <- temperoryDist
                prev[V] <- U
    return dist[], prev[]

 

Example

Let us consider the below example to understand the algorithm. Choosing the starting vertex as assign 0 to it. And assign infinity path values to all other devices.

Example of dijkstras algorithm

Go to each vertex and update its path length

If the new path length is smaller than the previous path length then update it with a smaller value. As shown below we update vertex B from infinity to 10 and vertex C from infinity to 3.

updating the path length of each vertex

Now select the vertex with the smaller path length as visited vertex and put it in the answer.

selecting the vertex with the smaller path length

Visit its neighbouring nodes of visited vertex and update the path lengths as required. Do not update the path length of the already visited vertex.

visiting the neighbouring nodes

Therefore, after each loop, we consider the unvisited vertex with the smaller path length.

considering the unvisited vertex

Repeat the process until all vertices have been visited

checking if all the vertexes has been visited

vertexes visited or not

final output of dijkstras algorithm

C++ code for Dijkstra’s Algorithm

#include
#include     
using namespace std;

int miniDist(int distance[], bool Tset[]) // finding minimum distance
{
    int minimum=INT_MAX,ind;
              
    for(int k=0;k<6;k++) 
    {
        if(Tset[k]==false && distance[k]<=minimum)      
        {
            minimum=distance[k];
            ind=k;
        }
    }
    return ind;
}

void DijkstraAlgo(int graph[6][6],int src) // adjacency matrix 
{
    int distance[6]; // // array to calculate the minimum distance for each node                             
    bool Tset[6];// boolean array to mark visited and unvisited for each node
    
     
    for(int k = 0; k<6; k++)
    {
        distance[k] = INT_MAX;
        Tset[k] = false;    
    }
    
    distance[src] = 0;   // Source vertex distance is set 0               
    
    for(int k = 0; k<6; k++)                           
    {
        int m=miniDist(distance,Tset); 
        Tset[m]=true;
        for(int k = 0; k<6; k++)                  
        {
            // updating the distance of neighbouring vertex
            if(!Tset[k] && graph[m][k] && distance[m]!=INT_MAX && distance[m]+graph[m][k]<distance[k])
                distance[k]=distance[m]+graph[m][k];
        }
    }
    cout<<"Vertex\t\tDistance from source vertex"<<endl;
    for(int k = 0; k<6; k++)                      
    { 
        char str=65+k; 
        cout<<str<<"\t\t\t"<<distance[k]<<endl;
    }
}

int main()
{
    int graph[6][6]={
        {0, 1, 2, 0, 0, 0},
        {1, 0, 0, 5, 1, 0},
        {2, 0, 0, 2, 3, 0},
        {0, 5, 2, 0, 2, 2},
        {0, 1, 3, 2, 0, 1},
        {0, 0, 0, 2, 1, 0}};
    DijkstraAlgo(graph,0);
    return 0;                           
}

 

Output

Vertex         Distance from source

A                     0

B                     1

C                     2

D                     4

E                     2

F                     3

Application

  1. Dijkstra’s algorithm is used as a routing protocol required by the routers to update their forwarding table.
  2. It is used to find the shortest distance between two locations along the path on google maps.
  3. It is used in telephone networking to find the shortest path for finding the nearest switching station for transmission.
  4. Dijkstra’s algorithm is used to find the shortest path between users measured through handshakes or connection among them.
  5. Dijkstra’s algorithm is used to minimize the number of hops in computer networks.

Conclusion

As Dijkstra's algorithm has its own importance in the real world, it is most recommended to learn and understand Dijkstra's algorithm. Therefore, in the above article, we studied what is Dijkstra's algorithm and its algorithm steps to get the result. We also studied the pseudo code and c++ code for finding the shortest path between two points aLong with the practical application of the algorithm.

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Shivali Bhadaniya
I'm Shivali Bhadaniya, a computer engineer student and technical content writer, very enthusiastic to learn and explore new technologies and looking towards great opportunities. It is amazing for me to share my knowledge through my content to help curious minds.