Shortest Path in Unweighted Graph Using BFS in DSA Java - Build from Scratch

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: You are working on a city map app that helps users find the shortest walking path between two places. The city map is represented as a graph where intersections are nodes and roads are edges. Since all roads are of equal length, the shortest path means the fewest roads to cross.

🎯 Goal: Build a Java program that finds the shortest path from a starting intersection to all other intersections using Breadth-First Search (BFS) on an unweighted graph.

📋 What You'll Learn

Create an adjacency list to represent the graph with 5 intersections (nodes).

Add a variable to store the starting node for BFS.

Implement BFS to find the shortest distance from the start node to all other nodes.

Print the shortest distances from the start node to each node.

💡 Why This Matters

🌍 Real World

Finding shortest paths in city maps, social networks, or computer networks where all connections have equal cost.

💼 Career

Understanding BFS and shortest path algorithms is essential for software engineers working on navigation apps, network routing, and graph-based data analysis.

1

Create the graph as an adjacency list

Create a Java Map<Integer, List<Integer>> called graph representing the city intersections and roads with these exact edges: 0 connected to 1 and 2, 1 connected to 0 and 3, 2 connected to 0 and 3 and 4, 3 connected to 1 and 2 and 4, 4 connected to 2 and 3.

DSA Java

// Your code here to create the graph adjacency list

Hint

Use a HashMap with Integer keys and List<Integer> values. Use Arrays.asList() to create the adjacency lists.

2

Add the start node variable

Add an integer variable called startNode and set it to 0 to represent the starting intersection for BFS.

DSA Java

import java.util.*;

public class ShortestPathBFS {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 3));
        graph.put(2, Arrays.asList(0, 3, 4));
        graph.put(3, Arrays.asList(1, 2, 4));
        graph.put(4, Arrays.asList(2, 3));

        // Add startNode variable here
        // Your code here
    }
}

Hint

Just create an integer variable startNode and assign it the value 0.

3

Implement BFS to find shortest distances

Write code to create an integer array distances of size 5 initialized with -1. Set distances[startNode] to 0. Use a Queue<Integer> called queue and add startNode to it. Then use a while loop to process nodes from queue. For each neighbor of the current node, if distances[neighbor] is -1, set it to distances[current] + 1 and add neighbor to queue. This finds shortest distances from startNode to all nodes.

DSA Java

import java.util.*;

public class ShortestPathBFS {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 3));
        graph.put(2, Arrays.asList(0, 3, 4));
        graph.put(3, Arrays.asList(1, 2, 4));
        graph.put(4, Arrays.asList(2, 3));

        int startNode = 0;

        // Implement BFS to find shortest distances
        // Your code here
    }
}

Hint

Use an array to track distances. Use a queue to explore nodes level by level. Update distances only if the node was not visited before (distance -1).

4

Print the shortest distances

Use a for loop with variable node from 0 to 4 to print the shortest distance from startNode to each node in the format: "Distance from 0 to node: distance".

DSA Java

import java.util.*;

public class ShortestPathBFS {
    public static void main(String[] args) {
        Map> graph = new HashMap();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 3));
        graph.put(2, Arrays.asList(0, 3, 4));
        graph.put(3, Arrays.asList(1, 2, 4));
        graph.put(4, Arrays.asList(2, 3));

        int startNode = 0;

        int[] distances = new int[5];
        Arrays.fill(distances, -1);
        distances[startNode] = 0;

        Queue queue = new LinkedList();
        queue.add(startNode);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int neighbor : graph.get(current)) {
                if (distances[neighbor] == -1) {
                    distances[neighbor] = distances[current] + 1;
                    queue.add(neighbor);
                }
            }
        }

        // Print shortest distances
        // Your code here
    }
}

Hint

Use a for loop from 0 to 4 and print each distance with System.out.println in the required format.

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