Shortest Path in Unweighted Graph (BFS)

Share

Given an unweighted, undirected graph with n nodes (labeled 0 to n-1) and a list of edges, find the length of the shortest path between a given source node and a destination node. If no path exists, return -1.

Example 1
Input: n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], src = 0, dst = 5
Output: 4
Explanation: Shortest path is 0 → 1 → 3 → 4 → 5, which has length 4.
Example 2
Input: n = 4, edges = [[0,1],[1,2]], src = 0, dst = 3
Output: -1
Explanation: Node 3 is disconnected; no path exists from 0 to 3.

Solution Approach

BFS is the natural choice for finding the shortest path in an unweighted graph because it explores nodes level by level, guaranteeing that the first time we reach the destination it is via the shortest route.

  • Build an adjacency list from the edge list.
  • Start BFS from the source node, maintaining a visited set to avoid revisiting nodes.
  • Track the current distance (level). For each neighbor not yet visited, enqueue it.
  • Return the distance when the destination is dequeued. If the queue empties without finding the destination, return -1.
Java
import java.util.*;

public class ShortestPathBFS {
    public int shortestPath(int n, int[][] edges, int src, int dst) {
        // Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(src);
        visited[src] = true;
        int distance = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                if (node == dst) return distance;
                for (int neighbor : adj.get(node)) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
            distance++;
        }
        return -1;
    }
}
Complexity Analysis:

Time complexity: O(V + E) where V is the number of vertices and E is the number of edges.
Space complexity: O(V + E) for the adjacency list, visited array, and BFS queue.