Graphs

Graph Patterns: Unweighted Shortest Path (BFS)

May 2026

6 min read

If a problem asks for the 'minimum steps' or 'shortest path' between two nodes in a graph where all edges are equal (unweighted), Depth-First Search will fail you. Breadth-First Search is mathematically required.

Introduction

Breadth-First Search (BFS) is the definitive algorithm for finding the shortest path in an unweighted graph.

Because BFS processes nodes level-by-level, it searches outward in concentric circles. It completely exhausts all nodes that are $1$ step away before it ever looks at nodes $2$ steps away. Therefore, the very first time BFS encounters the target node, it is absolutely guaranteed to be the shortest possible route.

The Level-Order Implementation

The key to tracking distance/steps in BFS is capturing the queue.size() at the start of the while loop.

By iterating exactly size times in an inner loop, you process an entire "generation" of nodes in one batch. Once that batch finishes, you safely increment your steps counter before moving to the next deeper level.

Implementation

java

class Solution {
    public int shortestPathBFS(int start, int target, ArrayList<ArrayList<Integer>> adj) {
        Queue<Integer> q = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        
        q.add(start);
        visited.add(start);
        int steps = 0;
        
        while (!q.isEmpty()) {
            int size = q.size();
            
            // Process all nodes at the current depth level
            for (int i = 0; i < size; i++) {
                int node = q.poll();
                
                if (node == target) return steps;
                
                for (int neighbor : adj.get(node)) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        q.add(neighbor);
                    }
                }
            }
            steps++; // Increment steps after a full level is exhausted
        }
        return -1; // Unreachable
    }
}