The Shortest Path problem is a cornerstone in computer science and graph theory, with applications ranging from network routing to geographic mapping. Dijkstra’s Algorithm is one of the most efficient methods for finding the shortest path between nodes in a graph, which may represent, for example, road networks. This article presents a comprehensive C++ program that implements Dijkstra’s Algorithm, complete with detailed explanations of its structure and functionality.

Program Structure

The C++ program to find the shortest path using Dijkstra’s Algorithm is organized into several key components:

• Graph Representation: The graph is represented using an adjacency list.
• Priority Queue: Utilizes a min-heap to efficiently select the next node with the smallest tentative distance.
• Dijkstra’s Algorithm Implementation: Core logic to compute the shortest paths from the source node to all other nodes.
• Main Function: Handles input, invokes the algorithm, and displays the results.

Code Implementation

The following C++ program implements Dijkstra’s Algorithm to find the shortest path in a graph:

// Dijkstra's Algorithm to Find the Shortest Path in C++
// This program finds the shortest path from a source node to all other nodes in a weighted, directed graph.

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for pair
#include <limits> // for numeric_limits

using namespace std;

// Function to perform Dijkstra's Algorithm
vector<int> dijkstra(int V, vector<vector<pair<int, int>>> &adj, int src) {
    // Initialize distances to all vertices as infinity
    vector<int> dist(V, numeric_limits<int>::max());

    // Priority queue to select the vertex with the smallest distance
    // The pair contains (distance, vertex)
    priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> pq;

    // Distance to the source is 0
    dist[src] = 0;
    pq.push(make_pair(0, src));

    while(!pq.empty()) {
        // Extract the vertex with the minimum distance
        int u = pq.top().second;
        pq.pop();

        // Iterate through all adjacent vertices of u
        for(auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // If a shorter path to v is found
            if(dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return dist;
}

int main() {
    int V, E;
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    // Adjacency list representation
    // Each element is a pair (neighbor, weight)
    vector<vector<pair<int, int>>> adj(V, vector<pair<int, int>>());

    cout << "Enter the edges in the format (source destination weight):\n";
    for(int i = 0; i < E; i++) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
        adj[src].emplace_back(dest, weight);
        // If the graph is undirected, add the reverse edge as well
        // adj[dest].emplace_back(src, weight);
    }

    int source;
    cout << "Enter the source vertex: ";
    cin >> source;

    vector<int> distances = dijkstra(V, adj, source);

    cout << "\nShortest distances from vertex " << source << ":\n";
    for(int i = 0; i < V; i++) {
        if(distances[i] == numeric_limits<int>::max()) {
            cout << "Vertex " << i << ": Unreachable\n";
        }
        else {
            cout << "Vertex " << i << ": " << distances[i] << "\n";
        }
    }

    return 0;
}
        

Program Explanation

The program implements Dijkstra’s Algorithm to find the shortest path from a source vertex to all other vertices in a weighted graph. Below is a detailed breakdown of its components:

1. Graph Representation

The graph is represented using an adjacency list, where each vertex has a list of pairs representing its adjacent vertices and the corresponding edge weights.

vector<vector<pair<int, int>>> adj(V, vector<pair<int, int>>());

2. Dijkstra’s Algorithm Function

The dijkstra function computes the shortest distances from the source vertex to all other vertices using a priority queue (min-heap) to efficiently select the next vertex with the smallest tentative distance.

Function Prototype

vector<int> dijkstra(int V, vector<vector<pair<int, int>>> &adj, int src)

Parameters

• int V: Number of vertices in the graph.
• vector<vector<pair<int, int>>> &adj: Adjacency list representing the graph.
• int src: Source vertex from which shortest paths are calculated.

Return Value

• A vector of integers where the ith element represents the shortest distance from the source vertex to vertex i.

Algorithm Steps

1. Initialize a distance vector with all values set to infinity, except the source vertex which is set to 0.
2. Use a priority queue to store pairs of (distance, vertex), starting with the source vertex.
3. While the priority queue is not empty:
   • Extract the vertex with the minimum distance.
   • Iterate through all adjacent vertices of the extracted vertex.
   • If a shorter path to an adjacent vertex is found, update its distance and add it to the priority queue.
4. Return the distance vector containing the shortest distances to all vertices.

3. Main Function

The main function handles user input, initializes the graph, invokes the Dijkstra’s algorithm function, and displays the results.

Steps in Main Function

1. Prompt the user to enter the number of vertices and edges.
2. Read the edges along with their weights and populate the adjacency list.
3. Prompt the user to enter the source vertex.
4. Call the dijkstra function to compute the shortest distances.
5. Display the shortest distances from the source vertex to all other vertices.

Program Documentation

Detailed documentation for each component of the program:

vector<vector<pair<int, int>>> adj

• Purpose: Represents the graph using an adjacency list.
• Structure: A vector where each element is a vector of pairs. Each pair contains a neighboring vertex and the weight of the edge connecting them.

vector<int> dijkstra(int V, vector<vector<pair<int, int>>> &adj, int src)

• Purpose: Computes the shortest paths from the source vertex to all other vertices in the graph.
• Parameters:
  • int V: Number of vertices.
  • vector<vector<pair<int, int>>> &adj: Adjacency list of the graph.
  • int src: Source vertex.
• Returns: A vector containing the shortest distances from the source to each vertex.

Function: dijkstra

• Purpose: Implements Dijkstra’s Algorithm using a priority queue to efficiently find the shortest paths.
• Logic:
  • Initialize all distances to infinity except the source.
  • Use a min-heap priority queue to select the next vertex with the smallest tentative distance.
  • Update the distances of adjacent vertices if a shorter path is found.

Function: main

• Purpose: Acts as the entry point of the program, handling input/output operations.
• Process:
  1. Reads the number of vertices and edges from the user.
  2. Populates the adjacency list based on user input.
  3. Reads the source vertex.
  4. Calls the dijkstra function to compute shortest paths.
  5. Displays the shortest distances to all vertices.
• Return: Returns 0 upon successful execution.

How the Program Works

1. Input Handling: The program begins by prompting the user to enter the number of vertices (V) and edges (E). It then reads each edge’s source, destination, and weight, populating the adjacency list accordingly.
2. Initializing Distances: A distance vector is initialized with all values set to infinity, except for the source vertex, which is set to 0.
3. Priority Queue Setup: A priority queue (min-heap) is used to keep track of vertices to be processed, ordered by their current tentative distance.
4. Algorithm Execution: The algorithm repeatedly extracts the vertex with the smallest distance from the priority queue and updates the distances of its adjacent vertices if a shorter path is found.
5. Result Display: After processing all vertices, the program outputs the shortest distances from the source vertex to every other vertex in the graph.

Example Execution

Consider the following example graph:

Enter the number of vertices: 5
Enter the number of edges: 6
Enter the edges in the format (source destination weight):
0 1 10
0 2 3
1 2 1
1 3 2
2 1 4
2 3 8
3 4 7
0
        

Running the program with the above input will produce the following output:

Shortest distances from vertex 0:
Vertex 0: 0
Vertex 1: 7
Vertex 2: 3
Vertex 3: 9
Vertex 4: 16
        

This indicates that the shortest distance from vertex 0 to:

• Vertex 0 is 0 (itself).
• Vertex 1 is 7.
• Vertex 2 is 3.
• Vertex 3 is 9.
• Vertex 4 is 16.

Conclusion

Dijkstra’s Algorithm is a powerful and efficient method for finding the shortest paths in weighted graphs. This C++ implementation leverages an adjacency list and a priority queue to optimize performance, especially for large graphs. Understanding and implementing Dijkstra’s Algorithm is essential for solving various real-world problems related to network routing, geographic mapping, and resource optimization.