Shortest Path in Unweighted Graph Using BFS in DSA Java

Mental Model

We find the shortest path by exploring neighbors level by level, like ripples spreading in water.

Analogy: Imagine you are in a maze and shout out loud. The sound reaches rooms closest to you first, then rooms farther away. The first time the sound reaches a room is the shortest path to that room.

Graph:
0 -> 1 -> 2
↓    ↓
3    4

Start at node 0, find shortest path to node 4.

0 [start]
|
1
|
4 [target]

Dry Run Walkthrough

Input: Graph edges: 0-1, 0-3, 1-2, 1-4; Find shortest path from 0 to 4

Goal: Find the shortest number of edges from node 0 to node 4

Step 1: Start BFS from node 0, mark distance 0

Queue: [0]
Distances: 0=0, others=∞

Why: We begin from the start node with distance zero

Step 2: Dequeue 0, enqueue neighbors 1 and 3 with distance 1

Queue: [1, 3]
Distances: 0=0, 1=1, 3=1, others=∞

Why: Neighbors of 0 are one step away

Step 3: Dequeue 1, enqueue neighbors 2 and 4 with distance 2

Queue: [3, 2, 4]
Distances: 0=0, 1=1, 3=1, 2=2, 4=2

Why: Neighbors of 1 are two steps away from start

Step 4: Dequeue 3, no new neighbors to enqueue

Queue: [2, 4]
Distances unchanged

Why: 3's neighbors are already visited or none

Step 5: Dequeue 2, no new neighbors to enqueue

Queue: [4]
Distances unchanged

Why: 2's neighbors are already visited or none

Step 6: Dequeue 4, target found with distance 2

Queue: []
Distances: 4=2

Why: We reached the target node with shortest path length

Result:

Shortest path distance from 0 to 4 is 2

Annotated Code

DSA Java

import java.util.*;

public class ShortestPathBFS {
    static class Graph {
        int vertices;
        List<List<Integer>> adjList;

        Graph(int v) {
            vertices = v;
            adjList = new ArrayList<>();
            for (int i = 0; i < v; i++) {
                adjList.add(new ArrayList<>());
            }
        }

        void addEdge(int src, int dest) {
            adjList.get(src).add(dest);
            adjList.get(dest).add(src); // undirected graph
        }
    }

    public static int shortestPath(Graph graph, int start, int target) {
        int[] distance = new int[graph.vertices];
        Arrays.fill(distance, -1); // -1 means unvisited
        Queue<Integer> queue = new LinkedList<>();

        distance[start] = 0; // start node distance is 0
        queue.offer(start);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (current == target) {
                return distance[current]; // found shortest path
            }
            for (int neighbor : graph.adjList.get(current)) {
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[current] + 1; // update distance
                    queue.offer(neighbor); // enqueue neighbor
                }
            }
        }
        return -1; // target not reachable
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(1, 2);
        graph.addEdge(1, 4);

        int start = 0;
        int target = 4;
        int result = shortestPath(graph, start, target);
        System.out.println("Shortest path distance from " + start + " to " + target + " is " + result);
    }
}

distance[start] = 0; // start node distance is 0

initialize start node distance to zero

queue.offer(start);

enqueue start node to begin BFS

int current = queue.poll();

dequeue current node to explore neighbors

if (current == target) { return distance[current]; }

stop BFS when target node is reached

for (int neighbor : graph.adjList.get(current)) {

iterate over neighbors of current node

if (distance[neighbor] == -1) {

check if neighbor is unvisited

distance[neighbor] = distance[current] + 1;

update neighbor distance as one more than current

queue.offer(neighbor);

enqueue neighbor for future exploration

Output

Shortest path distance from 0 to 4 is 2

Complexity Analysis

Time: O(V + E) because BFS visits every vertex and edge once

Space: O(V) for the distance array and queue storing vertices

vs Alternative: Compared to DFS which may explore longer paths first, BFS guarantees shortest path in unweighted graphs efficiently

Edge Cases

Start node equals target node

Returns distance 0 immediately

DSA Java

if (current == target) { return distance[current]; }

Target node unreachable

Returns -1 indicating no path found

DSA Java

return -1; // target not reachable

Graph with isolated nodes

Distances remain -1 for unreachable nodes

DSA Java

if (distance[neighbor] == -1)

When to Use This Pattern

When asked for shortest path in an unweighted graph, use BFS because it explores nodes in order of distance from start, ensuring shortest path.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing, causing repeated visits
Fix: Mark distance or visited status immediately when enqueueing neighbors

Mistake: Using DFS which does not guarantee shortest path in unweighted graphs
Fix: Use BFS to ensure shortest path by level order traversal

Summary

Finds shortest path length in an unweighted graph using breadth-first search.

Use when you need the minimum number of edges between two nodes in an unweighted graph.

The key insight is BFS explores nodes in layers, so the first time you reach a node is the shortest path.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The shortest path from a start node to all other nodes

B. The node with the highest degree

C. The longest path between two nodes

D. The total number of edges in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node, visiting all neighbors before moving deeper.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance, the first time it reaches a node is via the shortest path.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option A

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS visits nodes by distance layers to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS works only for weighted graphs

2. Which Java data structure is commonly used to implement BFS for shortest path in an unweighted graph?

easy

A. Queue

B. PriorityQueue

C. HashMap

D. Stack

Solution

1. Step 1: Recall BFS traversal order

   BFS explores nodes in a first-in, first-out order to visit neighbors level by level.

2. Step 2: Identify the correct data structure

   A Queue supports FIFO order, making it ideal for BFS traversal.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   BFS uses Queue for level order traversal [OK]

Hint: Use Queue for FIFO order in BFS traversal [OK]

Common Mistakes:

• Using Stack which is LIFO and suits DFS
• Confusing PriorityQueue with Queue
• Using HashMap which stores key-value pairs, not order

3. What is the output distance array after running BFS from node 0 on this graph?

Graph edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4

Assume nodes are 0 to 4 and distance to start node is 0.

medium

A. [0, 0, 0, 0, 0]

B. [0, 1, 2, 3, 4]

C. [0, 1, 1, 1, 2]

D. [0, 1, 1, 2, 3]

Solution

1. Step 1: Start BFS from node 0 and set distance 0

   Distance[0] = 0. Neighbors 1 and 2 get distance 1.

2. Step 2: Visit neighbors of 1 and 2

   Node 3 is neighbor of both 1 and 2, first reached at distance 2.

3. Step 3: Visit neighbor of 3

   Node 4 is neighbor of 3, distance is 3.

4. Final Answer:

   [0, 1, 1, 2, 3] -> Option D

5. Quick Check:

   Distances increase by 1 per BFS level [OK]

Hint: Distance increments by 1 each BFS layer from start [OK]

Common Mistakes:

• Assigning wrong distances to node 3
• Confusing BFS with DFS distances
• Setting all distances to zero

4. Identify the error in this BFS code snippet for shortest path:

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Queue<Integer> q = new LinkedList<>();
q.add(start);
dist[start] = 0;
while(!q.isEmpty()) {
  int u = q.poll();
  for(int v : graph.get(u)) {
    if(dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.add(v);
    }
  }
}

medium

A. The queue should be a Stack for BFS

B. Distance array should be initialized with zeros

C. The condition 'dist[v] == 0' should check for Integer.MAX_VALUE instead

D. The start node distance should be Integer.MAX_VALUE

Solution

1. Step 1: Understand distance initialization

   Distances are set to Integer.MAX_VALUE to mark unvisited nodes.

2. Step 2: Check visitation condition

   Condition 'dist[v] == 0' wrongly checks for zero, but unvisited nodes have Integer.MAX_VALUE.

3. Step 3: Correct condition

   Change condition to 'dist[v] == Integer.MAX_VALUE' to detect unvisited nodes properly.

4. Final Answer:

   The condition 'dist[v] == 0' should check for Integer.MAX_VALUE instead -> Option C

5. Quick Check:

   Check unvisited nodes by Integer.MAX_VALUE [OK]

Hint: Check unvisited nodes by initial max distance, not zero [OK]

Common Mistakes:

• Using zero to check unvisited nodes when distances initialized to max
• Using Stack instead of Queue for BFS
• Incorrect distance initialization

5. Given an unweighted graph with nodes 0 to 5 and edges:

0-1, 0-2, 1-3, 2-3, 3-4, 4-5

If BFS starts at node 0, what is the shortest path from node 0 to node 5?

hard

A. [0, 1, 2, 3, 4, 5]

B. [0, 1, 3, 4, 5]

C. [0, 2, 3, 5]

D. [0, 2, 4, 5]

Solution

1. Step 1: Run BFS to find shortest distances

   Distances: 0->0, 1->1, 2->1, 3->2, 4->3, 5->4.

2. Step 2: Trace shortest path from 5 back to 0

   From 5 to 4, 4 to 3, 3 to 1 or 2, choose 1 for shortest path: 0->1->3->4->5.

3. Final Answer:

   [0, 1, 3, 4, 5] -> Option B

4. Quick Check:

   Shortest path follows BFS layers [OK]

Hint: Trace path backward from target using distances [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS distances
• Skipping nodes in path
• Confusing BFS with DFS path