BFS Shortest Path in Unweighted Graph

Find shortest path between two vertices in an unweighted graph using BFS traversal

Language Selection

Choose your preferred programming language

Showing: Python

BFS Shortest Path in Unweighted Graph

Problem Statement

Given an unweighted graph and two vertices (source and target), find the shortest path between them. In an unweighted graph, BFS guarantees finding the shortest path in terms of number of edges.

BFS explores vertices level by level, ensuring that when we first reach the target vertex, we’ve found the shortest path.

Input/Output Specifications

Input: An unweighted graph represented as:
- n vertices (numbered 0 to n-1)
- List of edges edges where each edge is [u, v]
- Source vertex source
- Target vertex target
Output:
- Shortest distance (number of edges) from source to target
- Or the actual shortest path as a list of vertices

Constraints

0 <= n <= 10^4
0 <= edges.length <= min(n*(n-1)/2, 10^4)
0 <= edges[i][0], edges[i][1] < n
0 <= source, target < n
Graph may be disconnected

Examples

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], source = 0, target = 5
Output: distance = 4, path = [0,1,3,4,5] or [0,2,3,4,5]
Explanation: 
0---1---3---4---5
|   |   |   |
2-------/   /
Shortest path has 4 edges

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[2,3]], source = 0, target = 3
Output: distance = 3, path = [0,1,2,3]
Explanation: Linear path from 0 to 3

Example 3:

Input: n = 4, edges = [[0,1],[2,3]], source = 0, target = 3
Output: distance = -1, path = []
Explanation: No path exists between disconnected components

Solution Approaches

Approach 1: BFS for Shortest Distance (Optimal)

Algorithm Explanation:

Use BFS starting from source vertex
Track distance from source to each vertex
When target is reached, return the distance
If target is not reachable, return -1

Implementation:

Python:

from collections import deque, defaultdict

def shortest_path_bfs(n, edges, source, target):
    """
    Find shortest distance using BFS
    Time: O(V + E)
    Space: O(V)
    """
    if source == target:
        return 0
    
    # Build adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # BFS
    queue = deque([source])
    visited = set([source])
    distance = 0
    
    while queue:
        size = len(queue)
        distance += 1
        
        for _ in range(size):
            current = queue.popleft()
            
            for neighbor in graph[current]:
                if neighbor == target:
                    return distance
                
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    
    return -1  # Target not reachable

def shortest_path_with_distances(n, edges, source, target):
    """
    BFS with distance array tracking
    Time: O(V + E)
    Space: O(V)
    """
    if source == target:
        return 0
    
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    distances = [-1] * n
    distances[source] = 0
    queue = deque([source])
    
    while queue:
        current = queue.popleft()
        
        for neighbor in graph[current]:
            if distances[neighbor] == -1:  # Not visited
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
                
                if neighbor == target:
                    return distances[neighbor]
    
    return -1

Java:

class Solution {
    /**
     * Find shortest distance using BFS
     * Time: O(V + E)
     * Space: O(V)
     */
    public int shortestPathBFS(int n, int[][] edges, int source, int target) {
        if (source == target) return 0;
        
        // Build adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        // BFS
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        
        queue.offer(source);
        visited[source] = true;
        int distance = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            distance++;
            
            for (int i = 0; i < size; i++) {
                int current = queue.poll();
                
                for (int neighbor : graph.get(current)) {
                    if (neighbor == target) {
                        return distance;
                    }
                    
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }
        }
        
        return -1;
    }
    
    /**
     * BFS with distance array tracking
     */
    public int shortestPathWithDistances(int n, int[][] edges, int source, int target) {
        if (source == target) return 0;
        
        List<List<Integer>> graph = buildGraph(n, edges);
        
        int[] distances = new int[n];
        Arrays.fill(distances, -1);
        distances[source] = 0;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int neighbor : graph.get(current)) {
                if (distances[neighbor] == -1) {
                    distances[neighbor] = distances[current] + 1;
                    queue.offer(neighbor);
                    
                    if (neighbor == target) {
                        return distances[neighbor];
                    }
                }
            }
        }
        
        return -1;
    }
    
    private List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        return graph;
    }
}

Go:

// shortestPathBFS - Find shortest distance using BFS
// Time: O(V + E)
// Space: O(V)
func shortestPathBFS(n int, edges [][]int, source, target int) int {
    if source == target {
        return 0
    }
    
    // Build adjacency list
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    
    // BFS
    queue := []int{source}
    visited := make([]bool, n)
    visited[source] = true
    distance := 0
    
    for len(queue) > 0 {
        size := len(queue)
        distance++
        
        for i := 0; i < size; i++ {
            current := queue[0]
            queue = queue[1:]
            
            for _, neighbor := range graph[current] {
                if neighbor == target {
                    return distance
                }
                
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }
    }
    
    return -1
}

// shortestPathWithDistances - BFS with distance array
func shortestPathWithDistances(n int, edges [][]int, source, target int) int {
    if source == target {
        return 0
    }
    
    // Build graph
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    
    distances := make([]int, n)
    for i := range distances {
        distances[i] = -1
    }
    distances[source] = 0
    
    queue := []int{source}
    
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        
        for _, neighbor := range graph[current] {
            if distances[neighbor] == -1 {
                distances[neighbor] = distances[current] + 1
                queue = append(queue, neighbor)
                
                if neighbor == target {
                    return distances[neighbor]
                }
            }
        }
    }
    
    return -1
}

// BFS with custom queue for better performance
type Queue struct {
    items []int
    front int
}

func NewQueue() *Queue {
    return &Queue{items: make([]int, 0), front: 0}
}

func (q *Queue) Enqueue(item int) {
    q.items = append(q.items, item)
}

func (q *Queue) Dequeue() int {
    if q.IsEmpty() {
        return -1
    }
    item := q.items[q.front]
    q.front++
    return item
}

func (q *Queue) IsEmpty() bool {
    return q.front >= len(q.items)
}

func (q *Queue) Size() int {
    return len(q.items) - q.front
}

func shortestPathOptimized(n int, edges [][]int, source, target int) int {
    if source == target {
        return 0
    }
    
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    
    queue := NewQueue()
    visited := make([]bool, n)
    
    queue.Enqueue(source)
    visited[source] = true
    distance := 0
    
    for !queue.IsEmpty() {
        size := queue.Size()
        distance++
        
        for i := 0; i < size; i++ {
            current := queue.Dequeue()
            
            for _, neighbor := range graph[current] {
                if neighbor == target {
                    return distance
                }
                
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue.Enqueue(neighbor)
                }
            }
        }
    }
    
    return -1
}

JavaScript:

/**
 * Find shortest distance using BFS
 * Time: O(V + E)
 * Space: O(V)
 */
function shortestPathBFS(n, edges, source, target) {
    if (source === target) return 0;
    
    // Build adjacency list
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    // BFS
    const queue = [source];
    const visited = new Set([source]);
    let distance = 0;
    
    while (queue.length > 0) {
        const size = queue.length;
        distance++;
        
        for (let i = 0; i < size; i++) {
            const current = queue.shift();
            
            for (const neighbor of graph[current]) {
                if (neighbor === target) {
                    return distance;
                }
                
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
    }
    
    return -1;
}

/**
 * BFS with distance array tracking
 */
function shortestPathWithDistances(n, edges, source, target) {
    if (source === target) return 0;
    
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const distances = new Array(n).fill(-1);
    distances[source] = 0;
    const queue = [source];
    
    while (queue.length > 0) {
        const current = queue.shift();
        
        for (const neighbor of graph[current]) {
            if (distances[neighbor] === -1) {
                distances[neighbor] = distances[current] + 1;
                queue.push(neighbor);
                
                if (neighbor === target) {
                    return distances[neighbor];
                }
            }
        }
    }
    
    return -1;
}

/**
 * Optimized BFS using deque for better performance
 */
class Deque {
    constructor() {
        this.items = {};
        this.front = 0;
        this.rear = 0;
    }
    
    addBack(item) {
        this.items[this.rear] = item;
        this.rear++;
    }
    
    removeFront() {
        if (this.isEmpty()) return null;
        const item = this.items[this.front];
        delete this.items[this.front];
        this.front++;
        return item;
    }
    
    isEmpty() {
        return this.front === this.rear;
    }
    
    size() {
        return this.rear - this.front;
    }
}

function shortestPathOptimized(n, edges, source, target) {
    if (source === target) return 0;
    
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const queue = new Deque();
    const visited = new Array(n).fill(false);
    
    queue.addBack(source);
    visited[source] = true;
    let distance = 0;
    
    while (!queue.isEmpty()) {
        const size = queue.size();
        distance++;
        
        for (let i = 0; i < size; i++) {
            const current = queue.removeFront();
            
            for (const neighbor of graph[current]) {
                if (neighbor === target) {
                    return distance;
                }
                
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.addBack(neighbor);
                }
            }
        }
    }
    
    return -1;
}

C#:

public class Solution {
    /// <summary>
    /// Find shortest distance using BFS
    /// Time: O(V + E)
    /// Space: O(V)
    /// </summary>
    public int ShortestPathBFS(int n, int[][] edges, int source, int target) {
        if (source == target) return 0;
        
        // Build adjacency list
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        // BFS
        var queue = new Queue<int>();
        var visited = new bool[n];
        
        queue.Enqueue(source);
        visited[source] = true;
        int distance = 0;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            distance++;
            
            for (int i = 0; i < size; i++) {
                int current = queue.Dequeue();
                
                foreach (int neighbor in graph[current]) {
                    if (neighbor == target) {
                        return distance;
                    }
                    
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.Enqueue(neighbor);
                    }
                }
            }
        }
        
        return -1;
    }
    
    /// <summary>
    /// BFS with distance array tracking
    /// </summary>
    public int ShortestPathWithDistances(int n, int[][] edges, int source, int target) {
        if (source == target) return 0;
        
        var graph = BuildGraph(n, edges);
        
        int[] distances = new int[n];
        Array.Fill(distances, -1);
        distances[source] = 0;
        
        var queue = new Queue<int>();
        queue.Enqueue(source);
        
        while (queue.Count > 0) {
            int current = queue.Dequeue();
            
            foreach (int neighbor in graph[current]) {
                if (distances[neighbor] == -1) {
                    distances[neighbor] = distances[current] + 1;
                    queue.Enqueue(neighbor);
                    
                    if (neighbor == target) {
                        return distances[neighbor];
                    }
                }
            }
        }
        
        return -1;
    }
    
    private List<int>[] BuildGraph(int n, int[][] edges) {
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        return graph;
    }
    
    /// <summary>
    /// LINQ-based approach for concise code
    /// </summary>
    public int ShortestPathLinq(int n, int[][] edges, int source, int target) {
        if (source == target) return 0;
        
        var graph = edges
            .SelectMany(e => new[] { (e[0], e[1]), (e[1], e[0]) })
            .GroupBy(x => x.Item1)
            .ToDictionary(g => g.Key, g => g.Select(x => x.Item2).ToList());
        
        var queue = new Queue<int>();
        var visited = new HashSet<int>();
        
        queue.Enqueue(source);
        visited.Add(source);
        int distance = 0;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            distance++;
            
            for (int i = 0; i < size; i++) {
                int current = queue.Dequeue();
                
                if (graph.ContainsKey(current)) {
                    foreach (int neighbor in graph[current]) {
                        if (neighbor == target) return distance;
                        
                        if (!visited.Contains(neighbor)) {
                            visited.Add(neighbor);
                            queue.Enqueue(neighbor);
                        }
                    }
                }
            }
        }
        
        return -1;
    }
}

Approach 2: BFS with Path Reconstruction

Algorithm Explanation:

Use BFS with parent tracking to reconstruct the actual shortest path
When target is found, backtrack using parent pointers to build path
Return both distance and path

Implementation Example (Python):

def shortest_path_with_reconstruction(n, edges, source, target):
    """
    BFS with path reconstruction
    Time: O(V + E)
    Space: O(V)
    """
    if source == target:
        return 0, [source]
    
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    queue = deque([source])
    visited = set([source])
    parent = {source: None}
    
    while queue:
        current = queue.popleft()
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current
                queue.append(neighbor)
                
                if neighbor == target:
                    # Reconstruct path
                    path = []
                    node = target
                    while node is not None:
                        path.append(node)
                        node = parent[node]
                    path.reverse()
                    
                    return len(path) - 1, path
    
    return -1, []

def bfs_all_distances(n, edges, source):
    """
    Find shortest distances from source to all vertices
    Time: O(V + E)
    Space: O(V)
    """
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    distances = [-1] * n
    distances[source] = 0
    queue = deque([source])
    
    while queue:
        current = queue.popleft()
        
        for neighbor in graph[current]:
            if distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    
    return distances

Complexity Analysis:

Time Complexity: O(V + E) - Each vertex and edge is processed once
Space Complexity: O(V) - For queue, visited set, and auxiliary arrays

Trade-offs:

Level-by-level vs Distance Array: Level approach is more intuitive, distance array is more efficient
Early Termination: Can stop as soon as target is found
Path Reconstruction: Requires additional parent tracking

Key Insights

BFS Guarantee: In unweighted graphs, BFS finds shortest paths due to level-order exploration
First Occurrence: The first time we reach target vertex gives shortest distance
Queue Properties: FIFO ensures vertices at distance d are processed before distance d+1
Visited Tracking: Prevents cycles and ensures each vertex is processed once

Edge Cases

Source equals Target: Distance is 0, path is [source]
Disconnected Graph: No path exists, return -1
Self-loops: Don’t affect shortest path in unweighted graphs
Single Vertex: Trivial case
Linear Chain: Straightforward traversal

How Solutions Handle Edge Cases:

Source equals target: Early return with distance 0
Disconnected graph: BFS terminates without finding target
Self-loops: Visited check prevents infinite loops
Single vertex: Handled by base case
Linear chain: BFS processes level by level correctly

Test Cases

def test_shortest_path_bfs():
    # Basic case
    assert shortest_path_bfs(6, [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], 0, 5) == 4
    
    # Linear path
    assert shortest_path_bfs(4, [[0,1],[1,2],[2,3]], 0, 3) == 3
    
    # Disconnected components
    assert shortest_path_bfs(4, [[0,1],[2,3]], 0, 3) == -1
    
    # Source equals target
    assert shortest_path_bfs(4, [[0,1],[1,2]], 1, 1) == 0
    
    # Single edge
    assert shortest_path_bfs(2, [[0,1]], 0, 1) == 1
    
    # Triangle - multiple paths
    assert shortest_path_bfs(3, [[0,1],[1,2],[2,0]], 0, 2) == 1
    
    # Complex graph
    edges = [[0,1],[1,2],[2,3],[0,4],[4,5],[5,3]]
    assert shortest_path_bfs(6, edges, 0, 3) == 3
    
    # Path reconstruction test
    distance, path = shortest_path_with_reconstruction(4, [[0,1],[1,2],[2,3]], 0, 3)
    assert distance == 3 and path == [0,1,2,3]
    
    print("All tests passed!")

test_shortest_path_bfs()

Follow-up Questions

Weighted Graphs: How would you handle positive edge weights? (Use Dijkstra)
Multiple Targets: Find shortest distance to any of multiple target vertices?
All Pairs: Find shortest distances between all pairs of vertices?
K Shortest Paths: Find the k shortest paths between source and target?
Bidirectional BFS: Can you optimize for single source-target queries?

Common Mistakes

Wrong Queue Usage: Using stack instead of queue (gives DFS, not BFS)
- Problem: Doesn’t guarantee shortest path
- Solution: Use FIFO queue for BFS
Missing Visited Check: Not marking vertices as visited
- Problem: Infinite loops and incorrect results
- Solution: Mark vertex as visited when adding to queue
Early Termination Error: Not stopping when target is found
- Problem: Unnecessary computation
- Solution: Return immediately when target is reached
Level Counting Error: Incrementing distance incorrectly
- Problem: Wrong distance calculation
- Solution: Process all vertices at current level before incrementing

Interview Tips

Algorithm Choice: Explain why BFS works for unweighted shortest path
Implementation Variants: Know both level-by-level and distance array approaches
Optimization Discussion: Mention early termination and bidirectional BFS
Edge Cases: Always discuss disconnected graphs
Extensions: Be prepared to discuss weighted graph alternatives

Concept Explanations

BFS Properties: BFS explores vertices in order of increasing distance from source. This property guarantees that in unweighted graphs, the first time we reach a vertex is via the shortest path.

Queue vs Stack: The choice of data structure determines the traversal order. Queue (FIFO) gives breadth-first exploration, while stack (LIFO) gives depth-first exploration.

Level-by-Level Processing: Processing all vertices at distance d before moving to distance d+1 ensures shortest path optimality in unweighted graphs.

When to Apply: Use BFS shortest path for:

Unweighted graphs or graphs with uniform edge weights
Finding shortest paths in terms of number of edges
Social network analysis (degrees of separation)
Puzzle solving (minimum moves to reach goal state)
Grid-based pathfinding with unit costs