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.

    What is edge Relaxation in Dijkstra’s algorithm?
    Relaxing an edge in Dijkstra’s algorithm refers to updating the cost of all vertices connected to a vertex v, if those costs would be reduced by including vertex v in the path. Thus, if the source node is ( v ), then we check
    If ( distance [ adjacent-node ] > length-of-path-to-adjacent-node-from-current-source ( v ) + distance [ current-source-node ( v ) ] ) {
        distance [ adjacent-node ] = length-of-path-to-adjacent-node-from-current-source ( v ) + distance [ current-source-node ( v ) ]
    }
    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 positive 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-2024, Algotree.org.
All rights reserved.