Dijkstra’s Algorithm in C++ | Shortest Path Algorithm

In this post, we’ll look at what a graph is and how Dijkstra’s algorithm works. We’ll also look at Dijkstra’s algorithm and the c++ code that goes with it, as well as the results. We’ll also look into the algorithm’s practical applicability in the real world. So let’s get started!

What is Graph?

A graph is a non-linear data structure composed of nodes and edges. The vertices of the graph are the nodes, and the edges are the lines that link the nodes.

As a result, the graph can be described as a set of vertices and edges connecting the nodes. If we think of Facebook as a graph, the nodes are the people that are connected to each other, and the edges are the connections between them. As a result, graphs are data structures that are used to show the “connection” between pairs of components. 

Generally, there are two types of graph possible:

  1. Undirected Graph: In an undirected graph, you can move from one node to another in both directions for every pair of linked nodes.
  2. Directed Graph: The directed graph allows you to only proceed from one node to another in a certain direction for each pair of linked nodes. Arrows can be use to link two nodes as an edge. Furthermore, a weighted graph is a network made up of edges that have a certain “weight” or “cost,” which might reflect time, distance, or anything else that represents the “connection” between two nodes.

What is Dijkstra’s Algorithm?

Dijkstra’s algorithm is also known as the shortest path algorithm. It’s a graph-finding method that finds the shortest path between nodes. The technique constructs a tree of the shortest routes between the beginning source vertex and every other point in the graph. It varies from a minimal spanning tree in that the shortest distance between two vertices may not be shared by all of the graph’s vertices. The method operates by creating a network of nodes with the shortest distance to the source. Dijkstra’s method solves the problem and finds the appropriate approach using a greedy algorithm.

When Does Dijkstra’s Algorithm Fail

Dijkstra’s approach can only be use to graphs with positive weights. To find the shortest path between the nodes, the weights of the edges must be add while running an algorithm. If there are any negative weights in the graph, the algorithm will fail. Keep in mind that once a node is mark as “visited,” the current path to that node is the shortest path to that node. As a result, if you have negative weights, this step may change if the overall weight is reduced.

Furthermore, while learning Dijkstra’s algorithm, the question of whether it is BFS or DFS comes. That’s right, it’s neither. The priority-first algorithm devised by Dijkstra is a priority-first algorithm. However, when choosing between BFS and DFS algorithms, BFS will take priority over DFS. Basically, you can discover the key structure of BFS inside Dijkstra’s algorithm, but honestly, it is much more than the BFS algorithm.

Algorithm for Dijkstra’s in C++

Look at the steps below to learn more about how Dijkstra’s algorithm works behind the scenes:

  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 vertices 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 neighbor vertex of the 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 mark 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[]

C++ code for Dijkstra’s Algorithm

#include<iostream>
#include<climits>
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:

dijsktra's algorithm code example output

Time Complexity

Dijkstra’s approach has a time complexity of O(V^2), where V is the number of vertices in the graph. If the input graph is represent by an adjacency list (a graph representation technique), the time complexity can be decrease to O(E log V) by utilizing a binary heap.

Dijkstra’s algorithm has a space complexity of O(V), where V is the total number of vertices in the graph. This is due to the fact that all of these vertices must be store in the list as an output.

Applications

  1. The Dijkstra algorithm is a routing technique that routers employ to update their forwarding tables.
  2. On Google Maps, it’s use to find the shortest distance between two points along a path.
  3. In telephone networking, it is use to determine the shortest path to the nearest switching station for transmission.
  4. The Dijkstra method is use to determine the shortest path between users as determined by handshakes or connections.
  5. In computer networks, Dijkstra’s method is use to reduce the number of hops.

Conclusion

Graphs are use to link items, people, and entities, and Dijkstra’s algorithm will help you in determining the shortest distance between two points in a graph. Because Dijkstra’s algorithm is so important in the real world, it’s best to study and understand it properly.

That’s all for this article if you have any confusion contact us through our website or email us at [email protected] or by using LinkedIn

Suggested Articles:

  1. How to Initialize an Array in Java – [With Examples]

Leave a Comment