Shortest Path (Unweighted)

In an unweighted graph, the shortest path between two nodes is the one with the fewest edges. BFS explores nodes in order of increasing distance from the source, so the first time you reach the target you have a shortest path.

Why BFS Gives Shortest Path

BFS visits nodes in levels: first all nodes at distance 1, then distance 2, and so on.
So the first time you dequeue the target node, you have found a path with the minimum number of edges.
This holds for both explicit graphs (adjacency list) and implicit graphs (e.g. grid, state space).

Template

Java
int shortestPath(List<List<Integer>> graph, int start, int end) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[start] = 0;
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(start);

    while (!q.isEmpty()) {
        int u = q.poll();
        if (u == end) return dist[u];
        for (int v : graph.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.offer(v);
            }
        }
    }
    return -1; // unreachable
}

Use dist[v] == -1 (or a separate visited[]) to ensure each node is enqueued at most once.

Reconstructing the Path

To recover the actual path, keep a parent[] array: when you set dist[v] = dist[u] + 1, set parent[v] = u. Then from end walk back via parent to start and reverse the list.

Multi-Source

If multiple nodes are valid starting points, initialize the queue with all of them at distance 0. BFS then gives the shortest distance from any source to each node (useful for “nearest gate” type problems).

Summary

For unweighted graphs, BFS in level order finds shortest paths. Use a distance array and enqueue each node at most once. For weighted graphs, use Dijkstra or another shortest-path algorithm instead.