Dijkstra’s Algorithm | Single source shortest path

Dijkstra’s Algorithm solves the single source shortest path problem. It helps in finding the shortest path from source node (0) to all other nodes in a weighted graph G. Dijkstra’s Algorithm has various applications, including route planning, network optimization, and resource allocation.

In this post, we will explore the working principles of Dijkstra’s algorithm and provide a C++ implementation to find the shortest path in a weighted graph.

Dijkstra’s Algorithm

Dijkstra’s algorithm works based on the principle of Greedy-approach, gradually expanding the search space until the shortest path to the destination node is found. The algorithm maintains a priority queue to select the node with the smallest distance from the source node at each iteration.

Explanation

1. Initialize the weighted-graph G and assign initial distances to all nodes. Set the distance of the source node as 0 and all other nodes as infinity.
2. Create a priority queue pq to store nodes based on their distances. Enqueue the source node with a distance = 0 into pq.
3. Repeat until the priority queue becomes empty:
   • Extract the node with the smallest distance from the priority queue.
   • Explore all the neighboring nodes of the extracted node.
   • Update the distances of the neighboring nodes if a shorter path is found.
   • If the distance is updated, enqueue the neighbor into the priority queue.

After the algorithm terminates, the shortest path to each node from the source node is determined.

Dijkstra’s Algorithm Limitations

Dijkstra’s algorithm is a powerful algorithm for finding the shortest path in a graph. However, it does have some limitations:

1. Single-source shortest path: Dijkstra’s algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph. It cannot be directly applied to find the shortest path between multiple pairs of vertices.
2. Non-negative weights: Dijkstra’s algorithm assumes that all edge weights are non-negative. If the graph contains negative edge weights, the algorithm may not produce correct results.
3. No negative cycles: Dijkstra’s algorithm assumes that there are no negative cycles in the graph. A negative cycle is a cycle where the sum of the weights along the cycle is negative. If the graph contains negative cycles, the algorithm may run indefinitely or produce incorrect results.
4. Greedy nature: Dijkstra’s algorithm follows a greedy approach by selecting the vertex with the smallest distance at each step. While this works for finding the shortest path in many cases, it may not always produce the globally optimal solution.

Pseudocode

Initialize (G, s)
 for each v ∈ G[vertices]:
  d[v] = INF
 d[s] = 0

Dijkstra (G, s)
 s = 0
 Initialize (G, s)
 Enqueue(pq, s)
 while !pq.empty():
  u = Extract-Min(pq)
  for each v ∈ adjacent(u):
    if distance[v] > distance[u] + edge_weight[u, v]:
      distance[v] = distance[u] + edge_weight[u, v]
      Enqueue(pq, v)

Code Implementation

//
//  main.cpp
//  Dijkstra's Algorithm
//
//  Created by Himanshu on 27/05/23.
//
 
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
 
#define INF numeric_limits<int>::max()
#define N 5
 
typedef pair<int, int> graphNode; // pair (distance, node)
vector<graphNode> graph[N];
 
//Custom comparator
struct Compare {
    bool operator()(const graphNode& a, const graphNode& b) {
        return a.second > b.second;
    }
};
 
void printDistances(vector<int> distance) {
     
    for (int i = 0; i < N; ++i) {
        cout << "Distance from source (0) to node " << i << ": ";
        if (distance[i] == INF)
            cout<<"INF"<<endl;
        else
            cout<<distance[i]<<endl;
    }
     
}
 
void Dijkstra(int source, vector<int> &distance) {
     
    priority_queue<graphNode, vector<graphNode>, Compare> pq;
 
    distance[source] = 0;
    pq.push({source, 0});
 
    while (!pq.empty()) {
        int u = pq.top().first;
        pq.pop();
         
        for (auto edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
 
            if (distance[u] != INF && ((distance[u] + weight) < distance[v])) {
                distance[v] = distance[u] + weight;
                pq.push({v, distance[v]});
            }
        }
    }
}
 
void initializeGraph() {
     
    graph[0].push_back({1, 10});
    graph[0].push_back({3, 5});
     
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 2});
     
    graph[2].push_back({4, 4});
     
    graph[3].push_back({1, 3});
    graph[3].push_back({2, 9});
    graph[3].push_back({4, 2});
     
    graph[4].push_back({0, 7});
    graph[4].push_back({2, 6});
     
}
 
int main() {
    int source = 0; // source node
    vector<int> distance(N, INF); // distances from the source node
    initializeGraph();
     
    Dijkstra(source, distance);
    
    printDistances(distance);
 
    return 0;
}

Output

Distance from source (0) to node 0: 0
Distance from source (0) to node 1: 8
Distance from source (0) to node 2: 9
Distance from source (0) to node 3: 5
Distance from source (0) to node 4: 7

Time complexity (using min-priority queue): O((E + V) logV), where E is the number of edges and V is the number of vertices. In a dense graph where E is close to V^2, this can be simplified to O(E + V log V).