Shortest Path in an Unweighted Graph

Given an unweighted graph, a source vertex, and a destination vertex, find the shortest path from the source to the destination in the most optimal way.

Why BFS is Used

For a weighted graph, we must use algorithms like Dijkstra's ($O(E \log V)$) or Bellman-Ford ($O(V \cdot E)$). However, when the graph is unweighted (all edge weights are equal/1), we can solve this problem in optimal linear time $O(V + E)$ using a modified version of Breadth-First Search (BFS).

The Logic

During BFS, when we traverse from a vertex u to its neighbor v, v is guaranteed to be reached in the minimum number of steps from the source. To reconstruct the exact path:

We maintain a dist array/object where dist[i] stores the shortest distance of vertex i from the source.
We maintain a pred (predecessor) array/object where pred[i] stores the vertex from which i was visited.
Once the destination is reached, we backtrack from the destination to the source using pred pointers to build the path.

Visual Example

Let's find the shortest path from source 0 to destination 7 in this unweighted graph:

Path: 0 -> 3 -> 7
Shortest Path Length: 2 (measured in number of edges)

JavaScript Code Implementation

class Graph {
    constructor() {
        this.list = {};
    }
 
    addVertex(vertex) {
        if (!this.list[vertex]) this.list[vertex] = [];
    }
 
    addEdge(v1, v2) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.list[v1].push(v2);
        this.list[v2].push(v1);
    }
 
    // Finds the shortest path using BFS
    findShortestPath(source, destination) {
        const visited = {};
        const dist = {};
        const pred = {};
        const queue = [];
 
        // Initialize structures
        Object.keys(this.list).forEach(vertex => {
            visited[vertex] = false;
            dist[vertex] = Infinity;
            pred[vertex] = null;
        });
 
        // Setup source
        visited[source] = true;
        dist[source] = 0;
        queue.push(source);
 
        // BFS loop
        while (queue.length > 0) {
            const u = queue.shift();
 
            const neighbors = this.list[u] || [];
            for (let v of neighbors) {
                if (!visited[v]) {
                    visited[v] = true;
                    dist[v] = dist[u] + 1;
                    pred[v] = u;
                    queue.push(v);
 
                    // Optional early exit if we found the destination
                    if (v === destination) break;
                }
            }
        }
 
        // If destination was not reached
        if (dist[destination] === Infinity) {
            console.log("No path exists between source and destination.");
            return null;
        }
 
        // Reconstruct path by backtracking
        const path = [];
        let crawl = destination;
        while (crawl !== null) {
            path.push(crawl);
            crawl = pred[crawl];
        }
        path.reverse();
 
        return {
            distance: dist[destination],
            path: path
        };
    }
}
 
// Driver code matching the example
const g = new Graph();
g.addEdge("0", "1");
g.addEdge("0", "3");
g.addEdge("1", "2");
g.addEdge("2", "3");
g.addEdge("3", "7");
g.addEdge("3", "4");
g.addEdge("7", "4");
g.addEdge("7", "6");
g.addEdge("4", "5");
g.addEdge("6", "5");
 
const result = g.findShortestPath("0", "7");
if (result) {
    console.log("Shortest path length is:", result.distance);
    console.log("Path is:", result.path.join(" -> "));
}
/*
Output:
Shortest path length is: 2
Path is: 0 -> 3 -> 7
*/

Complexity Analysis

Time Complexity: $O(V + E)$
- The BFS traversal visits every reachable vertex and edge once.
- Reconstructing the path takes $O(V)$ time in the worst case (equal to path length).
Auxiliary Space: $O(V)$
- Storage required for visited, dist, pred structures and the BFS queue.

Applications of DFS Detect Cycle in Undirected Graph