Dijkstra's Algorithm in C++

The key points of Dijkstra’s single source shortest path algorithm is as below :

  • Dijkstra’s algorithm finds the shortest path in a weighted graph containing only positive edge weights from a single source.
  • It uses a priority-based set to select a node / vertex nearest to the source that has not been edge relaxed.
    Edge Relaxation
    If ( distance [ adjacent-node ] > length-of-path-to-adjacent-node-from-current-source + distance [ current-source-node ] ) {
        distance [ adjacent-node ] = length-of-path-to-adjacent-node-from-current-source + distance [ current-source-node ]
    }
    Note :
    a) The distance [ ] array stores the shortest distance of every node from the source-node.
    b) Dijkstra’s algorithm begins by initializing distance [ original_source ] = 0 i.e the distance from the first (original) source node to itself is 0 and
    distance [ all_other_nodes ] = ∞.
  • Since Dijkstra’s algorithm cannot handle negative edge weights, Bellman-Ford algorithm is used for finding the shortest path in a graph containing negative edge weights.
  • In a graph with only positive edge weights, Dijkstra’s algorithm with a set implementation runs faster in O ((E+V) log V) than Bellman-Ford O (E.V).
    E represents the edges and V represents the vertices in the graph.

Algorithm : Dijkstra’s Shortest Path C++

1.     Initialize the distance from the source node S to all other nodes as infinite (999999999999) and to itself as 0.
2.    Insert the pair of < distance , node > for source i.e < 0, S > in a priority-based SET [C++]
       where the priority of the elements in the set is based on the length of the distance.
3.    While the SET is not empty do
4.       pair_at_top = SET . top( );
         Remove the element from the top of the SET.
         current_source_node = pair_at_top . second.
5.       For every adjacent_node to current_source_node do
6.            If ( distance [ adjacent_node ] > length_of_path_to_adjacent_node_from_current_source + distance [ current_source_node ] ) then
7.                 distance [ adjacent_node ] = length_of_path_to_adjacent_node_from_current_source + distance [ current_source_node ]
8.                 Update the SET with the new pair < distance [ adjacent_node ], adjacent_node >

Below data structures are used for storing the graph before running Dijkstra’s algorithm
Adjacency List : List of pairs of adjacent nodes and their corresponding weights in the graph.

Dijkstras_ShortestPath_DataStructure

Dijkstra’s algorithm step-by-step

This example of Dijkstra’s algorithm finds the shortest distance of all the nodes in the graph from the single / original source node 0.

Step 1 : Initialize the distance of the source node to itself as 0 and to all other nodes as ∞.
             Insert the pair < distance_from_original_source, node > in the set.
             i.e Insert < 0, 0 > in the set as the distance from the original source (0) to itself is 0. Dijkstras_Shortest_Path_Step_1

Step 2 : Remove the topmost pair < 0, 0 > from the set and relax the edge going towards every adjacent node(s) from the original source node ( 0 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
0 1 distance [ 1 ] = ∞ distance [ 1 ] > distance_between [ 0 - 1 ] + distance [ 0 ]
i.e Since ∞ > 5 + 0
Update distance, i.e distance [ 1 ] = 5 and insert pair < 5, 1 > in the set.
0 2 distance [ 2 ] = ∞ distance [ 2 ] > distance_between [ 0 - 2 ] + distance [ 0 ]
i.e Since ∞ > 1 + 0
Update distance, i.e distance [ 2 ] = 1 and insert pair < 1, 2 > in the set.
0 3 distance [ 3 ] = ∞ distance [ 3 ] > distance_between [ 0 - 3 ] + distance [ 0 ]
i.e Since ∞ > 4 + 0
Update distance, i.e distance [ 3 ] = 4 and insert pair < 4, 3 > in the set.

Dijkstras_Shortest_Path_Step_2

Step 3 : Remove the topmost pair < 1, 2 > from the set and relax the edge going towards every adjacent node(s) from the current source ( 2 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
2 0 distance [ 0 ] = 0 distance [ 0 ] < distance_between [ 2 - 0 ] + distance [ 2 ]
i.e Since 0 < 1 + 1
No edge relaxation needed.
2 1 distance [ 1 ] = 5 distance [ 1 ] > distance_between [ 2 - 1 ] + distance [ 2 ]
i.e Since 5 > 3 + 1
Update distance, i.e distance [ 1 ] = 4 and insert pair < 4, 1 > in the set.
2 3 distance [ 3 ] = 4 distance [ 3 ] > distance_between [ 2 - 3 ] + distance [ 2 ]
i.e Since 4 > 2 + 1
Update distance, i.e distance [ 3 ] = 3 and insert pair < 3, 3 > in the set.
2 4 distance [ 4 ] = ∞ distance [ 4 ] > distance_between [ 2 - 4 ] + distance [ 2 ]
i.e Since ∞ > 1 + 1
Update distance, i.e distance [ 4 ] = 2 and insert pair < 2, 4 > in the set.

Dijkstras_Shortest_Path_Step_3

Step 4 : Remove the topmost pair < 2, 4 > from the set and relax the edge going towards every adjacent node(s) from the current source ( 4 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
4 1 distance [ 1 ] = 4 distance [ 1 ] < distance_between [ 4 - 1 ] + distance [ 4 ]
i.e Since 4 < 8 + 2
No edge relaxation needed.
4 2 distance [ 2 ] = 1 distance [ 2 ] < distance_between [ 4 - 2 ] + distance [ 4 ]
i.e Since 1 < 1 + 2
No edge relaxation needed.
4 3 distance [ 3 ] = 3 distance [ 3 ] < distance_between [ 4 - 3 ] + distance [ 4 ]
i.e Since 3 < 2 + 2
No edge relaxation needed.
4 5 distance [ 5 ] = ∞ distance [ 5 ] > distance_between [ 4 - 5 ] + distance [ 4 ]
i.e Since ∞ > 3 + 2
Update distance, i.e distance [ 5 ] = 5 and insert pair < 5, 5 > in the set.

Dijkstras_Shortest_Path_Step_4

Step 5 : Remove the topmost pair < 3, 3 > from the set and relax the edge going towards every adjacent node(s) from the current source ( 3 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
3 0 distance [ 0 ] = 0 distance [ 0 ] < distance_between [ 3 - 0 ] + distance [ 3 ]
i.e Since 0 < 4 + 3
No edge relaxation needed.
3 2 distance [ 2 ] = 1 distance [ 2 ] < distance_between [ 3 - 2 ] + distance [ 3 ]
i.e Since 1 < 2 + 3
No edge relaxation needed.
3 4 distance [ 4 ] = 2 distance [ 4 ] < distance_between [ 3 - 4 ] + distance [ 3 ]
i.e Since 2 < 2 + 3
No edge relaxation needed.
3 5 distance [ 5 ] = 5 distance [ 5 ] > distance_between [ 3 - 5 ] + distance [ 3 ]
i.e Since 5 > 1 + 3
Update distance, i.e distance [ 5 ] = 4 and insert pair < 4, 5 > in the set.

Dijkstras_Shortest_Path_Step_5

Step 6 : Remove the topmost pair < 4, 1 > from the set and relax the edge going towards every adjacent node(s) from the current source ( 1 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
1 0 distance [ 0 ] = 0 distance [ 0 ] < distance_between [ 1 - 0 ] + distance [ 1 ]
i.e Since 0 < 5 + 4
No edge relaxation needed.
1 2 distance [ 2 ] = 1 distance [ 2 ] < distance_between [ 1 - 2 ] + distance [ 1 ]
i.e Since 1 < 3 + 4
No edge relaxation needed.
1 4 distance [ 4 ] = 2 distance [ 4 ] < distance_between [ 1 - 4 ] + distance [ 1 ]
i.e Since 2 < 8 + 4
No edge relaxation needed.

Dijkstras_Shortest_Path_Step_6

Step 7 : Remove the topmost pair < 4, 5 > from the set and relax the edge going towards every adjacent node(s) from the current source ( 5 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
5 3 distance [ 3 ] = 3 distance [ 3 ] < distance_between [ 5 - 3 ] + distance [ 5 ]
i.e Since 3 < 1 + 4
No edge relaxation needed.
5 4 distance [ 4 ] = 2 distance [ 4 ] < distance_between [ 5 - 4 ] + distance [ 5 ]
i.e Since 2 < 3 + 4
No edge relaxation needed.

The algorithm terminates here as the set is empty and we have calculated the shortest path to all the nodes from the original source 0 as shown below.

Dijkstras_Shortest_Path_Step_7

Data structure used for running Dijkstra’s shortest path : Distance based priority set for choosing the vertex nearest to the source.
Graph type: Designed for weighted (directed / un-directed) graph containing positve edge weights.
Time complexity of Dijkstra’s algorithm : O ( (E+V) Log(V) ) for an adjacency list implementation of a graph. V is the number of vertices and E is the number of edges in a graph.

#include<iostream>
#include<vector>
#include<set>

using namespace std;
typedef pair<int,unsigned long long> PII;
typedef vector<PII> VPII;
typedef vector<VPII> VVPII;

void DijkstrasShortestPath (int source_node, int node_count, VVPII& graph) {

    // Assume that the distance from source_node to other nodes is infinite 
    // in the beginnging, i.e initialize the distance vector to a max value
    const long long INF = 999999999999;
    vector<unsigned long long> dist(node_count, INF);
    set<PII> set_length_node;
    
    // Distance from starting vertex to itself is 0
    dist[source_node] = 0;
    set_length_node.insert(PII(0,source_node));

    while (!set_length_node.empty()) {

        PII top = *set_length_node.begin();
        set_length_node.erase(set_length_node.begin());

        int current_source_node = top.second;

        for (auto& it : graph[current_source_node]) {

            int adj_node = it.first;
            int length_to_adjnode = it.second;
    
            // Edge relaxation 
            if (dist[adj_node] > length_to_adjnode + dist[current_source_node]) {
    
                // If the distance to the adjacent node is not INF, means the pair <dist, node> is in the set
                // Remove the pair before updating it in the set.
                if (dist[adj_node] != INF) {
                   set_length_node.erase(set_length_node.find(PII(dist[adj_node],adj_node))); 
                }
                dist[adj_node] = length_to_adjnode + dist[current_source_node];
                set_length_node.insert(PII(dist[adj_node], adj_node));
            }
        }
    }   

    for (int i=0; i<node_count; i++)
        cout << "Source Node(" << source_node << ") -> Destination Node(" << i << ") : " << dist[i] << endl;
}

int main(){

    vector<VPII> graph;

    // Node 0: <1,5> <2,1> <3,4>
    VPII a = {{1,5}, {2,1}, {3,4}};
    graph.push_back(a);

    // Node 1: <0,5> <2,3> <4,8>
    VPII b = {{0,5}, {2,3}, {4,8}};
    graph.push_back(b);

    // Node 2: <0,1> <1,3> <3,2> <4,1>
    VPII c = {{0,1}, {1,3}, {3,2}, {4,1}};
    graph.push_back(c);

    // Node 3: <0,4> <2,2> <4,2> <5,1>
    VPII d = {{0,4}, {2,2}, {4,2}, {5,1}};
    graph.push_back(d);

    // Node 4: <1,8> <2,1> <3,2> <5,3>
    VPII e = {{1,8}, {2,1}, {3,2}, {5,3}};
    graph.push_back(e);

    // Node 5: <3,1> <4,3> 
    VPII f = {{3,1}, {4,3}};
    graph.push_back(f);

    int node_count  = 6;

    int source_node = 0;
    DijkstrasShortestPath(source_node, node_count, graph);
    cout << endl;

    source_node = 5;
    DijkstrasShortestPath(source_node, node_count, graph);

    return 0;
}

Output

Source Node(0) -> Destination Node(0) : 0
Source Node(0) -> Destination Node(1) : 4
Source Node(0) -> Destination Node(2) : 1
Source Node(0) -> Destination Node(3) : 3
Source Node(0) -> Destination Node(4) : 2
Source Node(0) -> Destination Node(5) : 4

Source Node(5) -> Destination Node(0) : 4
Source Node(5) -> Destination Node(1) : 6
Source Node(5) -> Destination Node(2) : 3
Source Node(5) -> Destination Node(3) : 1
Source Node(5) -> Destination Node(4) : 3
Source Node(5) -> Destination Node(5) : 0

Copyright (c) 2019-2023, Algotree.org.
All rights reserved.