Shortest Path (Unweighted)

How It Works

In a graph where every edge costs the same, breadth-first search finds shortest paths by construction. The queue processes nodes in non-decreasing distance order: the source at distance 0, then all its neighbors at distance 1, and so on. The first time a node is dequeued, its recorded distance is provably minimal, because any shorter route would have enqueued it earlier. Marking nodes visited when they are enqueued — not when dequeued — prevents duplicates from bloating the queue.

BFS runs in O(V + E) time and O(V) space. Dijkstra's algorithm solves the same problem in O(E log V) with a priority queue; when all weights are equal, the plain FIFO queue replaces the heap and the log factor disappears.

Step-by-Step Visualization

Code

static int shortestPath(List<List<Integer>> graph, int start, int end) {
  Set<Integer> visited = new HashSet<>();
  visited.add(start);
  Queue<int[]> queue = new LinkedList<>();
  queue.add(new int[]{start, 0});

  while (!queue.isEmpty()) {
    int[] curr = queue.poll();
    int node = curr[0], dist = curr[1];
    if (node == end) return dist;
    for (int nei : graph.get(node)) {
      if (!visited.contains(nei)) {
        visited.add(nei);
        queue.add(new int[]{nei, dist + 1});
      }
    }
  }
  return -1;
}

Tips & Gotchas

Practice Problems

• 1Shortest Path in Binary Matrix
• 2Word Ladder
• 3Open the Lock
• 4Nearest Exit from Entrance in Maze

About the BFS Queue Pattern

BFS explores nodes level by level using a queue. Enqueue the starting node, then repeatedly: dequeue a node, process it, and enqueue all its unvisited neighbors. This guarantees you visit nodes in order of their distance from the start.

Common Queue / Deque Interview Problems

• Binary Tree Level Order Traversal
• Sliding Window Maximum
• Rotting Oranges
• Shortest Path in Binary Matrix
• Implement Queue using Stacks

Frequently Asked Questions

Other BFS Queue Techniques