Shortest Path in Graph - Dijkstra’s Algorithm | DSA in C++ - Software Development PDF Download

Introduction

When working with graphs, finding the shortest path between two vertices is a common problem. One popular algorithm for solving this problem is Dijkstra's algorithm. It is an efficient algorithm that can find the shortest path in a graph with non-negative edge weights. In this article, we will explore Dijkstra's algorithm, understand its implementation in C++, and go through some examples to solidify our understanding.

Dijkstra's Algorithm Overview

Dijkstra's algorithm works by iteratively selecting the vertex with the smallest distance from the source vertex and updating the distances of its adjacent vertices. It maintains a set of visited vertices and a priority queue to keep track of the vertices with their current distances from the source. The algorithm continues until all vertices have been visited or the target vertex has been reached.

Implementation in C++

To implement Dijkstra's algorithm in C++, we will need a few data structures:

• A graph representation: We can use an adjacency list to store the graph, where each vertex is associated with a list of its neighboring vertices and their corresponding edge weights.
• A priority queue: We need a data structure that supports efficient extraction of the vertex with the minimum distance from the source. The C++ Standard Library provides a 'priority_queue' container that we can utilize for this purpose.
• An array to track distances: We need to keep track of the current minimum distances from the source vertex to all other vertices. An array or vector can be used to store these distances.

Now, let's dive into the code implementation of Dijkstra's algorithm:

#include <iostream>

#include <queue>

#include <vector>

#include <climits>

using namespace std;

typedef pair<int, int> pii; // pair of vertex and distance

vector<int> dijkstra(vector<vector<pii>>& graph, int source) {

    int numVertices = graph.size();

    vector<int> distances(numVertices, INT_MAX); // Initialize distances with infinity

    distances[source] = 0; // Distance from source to itself is 0

   priority_queue<pii, vector<pii>, greater<pii>> pq; // Min-heap for prioritizing vertices

    pq.push({0, source}); // Push source vertex with distance 0

   while (!pq.empty()) {

        int u = pq.top().second;

        int dist = pq.top().first;

        pq.pop();

        // If we have already processed this vertex, continue

        if (dist > distances[u])

            continue;

        // Process all neighboring vertices of u

        for (auto& neighbor : graph[u]) {

            int v = neighbor.first;

            int weight = neighbor.second;

            // Relax the edge (u, v) if a shorter path is found

            if (dist + weight < distances[v]) {

                distances[v] = dist + weight;

                pq.push({distances[v], v});

            }

        }

    }

    return distances;

}

int main() {

    int numVertices = 6; // Number of vertices in the graph

    // Create the adjacency list representation of the graph

    vector<vector<pii>> graph(numVertices);

    // Add edges and their weights to the graph

    graph[0].push_back({1, 5}); // Edge: 0 --5--> 1

    graph[0].push_back({2, 3}); // Edge: 0 --3--> 2

    graph[1].push_back({3, 2}); // Edge: 1 --2--> 3

    graph[2].push_back({1, 1}); // Edge: 2 --1--> 1

    graph[2].push_back({3, 1}); // Edge: 2 --1--> 3

    graph[3].push_back({4, 3}); // Edge: 3 --3--> 4

    graph[4].push_back({5, 2}); // Edge: 4 --2--> 5

    int source = 0; // Source vertex

    // Find the shortest distances from the source vertex

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

    // Output the shortest distances

    cout << "Shortest distances from vertex " << source << ":\n";

    for (int i = 0; i < numVertices; ++i) {

        cout << "Vertex " << i << ": " << distances[i] << '\n';

    }

    return 0;

}

Explanation of the Code

Let's break down the code to understand its functionality:

• We include the necessary headers, define a 'typedef' for the pair of vertex and distance, and declare the necessary variables and data structures.
• The 'dijkstra' function takes the graph and the source vertex as input and returns a vector of distances.
• We initialize the distances vector with infinity ('INT_MAX') except for the source vertex, which is set to 0.
• We use a priority queue ('pq') to store the vertices based on their distances from the source. The priority queue is implemented as a min-heap using 'greater<pii>'.
• We push the source vertex with distance 0 into the priority queue.
• While the priority queue is not empty, we extract the vertex 'u' with the minimum distance from the source.
• If the extracted distance 'dist' is greater than the distance stored in the distances vector for 'u', it means we have already processed this vertex and we continue to the next iteration.
• We iterate through all neighboring vertices of 'u' and relax the edges if a shorter path is found.
• If the new distance is smaller than the current distance stored in the distances vector for the neighboring vertex 'v', we update the distance and push the updated distance and vertex pair into the priority queue.
• Finally, we return the distances vector.

Example

Let's consider a graph and find the shortest path using Dijkstra's algorithm. Here's the graph:

   5       3

0 -----> 1 -----> 2

 \       |

  \1     |1

   \     v

    ---> 3 -----> 4 -----> 5

       3       2

Input:

• Source vertex: 0

Output:

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

Sample Problems

Problem 1: Consider the following graph. Find the shortest path from vertex A to vertex E.

   6       4

A -----> B -----> C

 \       |       |

  \5     |3     |1

   \     v       v

    ---> D -----> E

       2       2

Input:

• Source vertex: A
• Target vertex: E

Output:

• Shortest path: A -> D -> E
• Shortest distance: 7

Problem 2: Given the following graph, find the shortest path from vertex S to vertex T.

    1       2

S -----> A -----> B

 \       |       |

  \1     |2     |3

   \     v       v

    ---> C -----> T

       3       1

Input:

• Source vertex: S
• Target vertex: T

Output:

• Shortest path: S -> C -> T
• Shortest distance: 4

Conclusion

Dijkstra's algorithm is a powerful tool for finding the shortest path in a graph with non-negative edge weights. By implementing the algorithm in C++, we can efficiently solve such problems. Remember to define the graph's structure, initialize the necessary data structures, and iterate through the vertices while updating the distances. With practice and application, you can master Dijkstra's algorithm and apply it to various graph problems.