C++ Program to Find the Shortest Path Between Two Nodes in an Unweighted Graph

1. Introduction

Finding the shortest path between two nodes is a classic problem in computer science. For unweighted graphs, the Breadth-First Search (BFS) algorithm is particularly efficient. Given a source vertex, BFS will explore its neighbors before proceeding to their neighbors, ensuring that the shortest path is identified as soon as the destination vertex is visited.

2. Program Overview

The program will:

1. Set up a Graph class using an adjacency list.

2. Implement functions in the Graph class to:

- Add edges to the graph.

- Find the shortest path from a source to a destination vertex.

3. Display the shortest path in the main function.

3. Code Program

#include<iostream>
#include<list>
#include<queue>
#include<vector>
using namespace std;

class Graph {
    int V;  // Number of vertices
    list<int> *adj;  // Adjacency lists

public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }

    // Function to add an edge to the graph
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    // Function to print shortest path from source to destination
    void shortestPath(int src, int dest) {
        // Mark all vertices as not visited
        vector<bool> visited(V, false);

        // Store source and its distance (distance of source from itself is 0)
        queue<pair<int, int>> q; // Pair: Node, Distance
        q.push({src, 0});

        visited[src] = true;

        while (!q.empty()) {
            int v = q.front().first;
            int dist = q.front().second;
            q.pop();

            // If the current vertex is the destination
            if (v == dest) {
                cout << "Shortest path length is: " << dist << endl;
                return;
            }

            // Otherwise enqueue its adjacent vertices
            for (int u : adj[v]) {
                if (!visited[u]) {
                    visited[u] = true;
                    q.push({u, dist + 1});
                }
            }
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    g.shortestPath(0, 3);

    return 0;
}

Output:

Shortest path length is: 2

4. Step By Step Explanation

1. The Graph is represented using adjacency lists.

2. The shortestPath function uses BFS. It maintains a queue of pairs, where each pair consists of a node and its distance from the source node.

3. When visiting a node, if it's the destination node, we print its distance (which would be the shortest because BFS checks nodes layer by layer).

4. If the current node is not the destination, we proceed to its non-visited neighbors.

5. In our main function, a graph is created, edges are added, and then the shortest path from vertex 0 to vertex 3 is computed and printed.

The code comments clarify the implementation steps and guide the reader through the BFS traversal.