Shortest Path in Undirected Graph with Unit Weights

1. Problem Statement & Overview

When given an undirected graph where every edge has a constant unit weight of 1, and a designated source node, the objective is to find the shortest distance from the source to every other node in the graph. If a particular node is completely unreachable from the source, its corresponding shortest distance must be denoted by -1.

Because all edge weights are identical ($w = 1$), the distances expand outward uniformly level by level. This structural uniformity allows us to bypass heavy algorithms like Dijkstra's priority queue and instead solve the problem optimally using a standard Breadth-First Search (BFS) traversal combined with a distance array.

2. Core Mental Model & BFS Intuition

To understand why a standard queue works for finding shortest paths here, consider how water ripples outward when a pebble is dropped into a pond.

Real-Life Analogy: Expanding Ripples in Water

Imagine standing at a central fountain (the source node) and throwing a stone in. The first wave of ripples reaches all adjacent benches at Distance 1. From those benches, the next wave reaches points at Distance 2, and so on. Because every step takes exactly 1 unit of time/distance, whatever reaches a spot first is guaranteed to have arrived via the shortest possible path.

In a queue-based BFS:

• The queue naturally orders nodes by their distance from the source.
• Nodes at distance 0 are processed first, followed strictly by nodes at distance 1, then 2, and so forth.
• We never need a complex priority queue or min-heap because the expansion order is intrinsically sorted by distance increments of +1.

3. Naive vs. Optimal Approach

4. Step-by-Step Algorithm Walkthrough

Let us trace an example graph with $8$ nodes (numbered $0$ to $7$) where node 0 is the source.

Initialization Phase

1. Distance Array: Create a dist array of size $9$ (to accommodate index $8$), initialized with a very large number representing infinity (1e9 or a sentinel like 189). Set dist[source] = 0 (e.g., dist[0] = 0).
2. Queue Setup: Declare a standard FIFO queue and push the source with its initial distance: q.push({0, 0}) (node 0, distance 0).
3. Answer Array: Prepare an answer array initialized to -1 for all nodes.

Traversal Flow

Queue initially: [ (0, 0) ]
Dist array: [0, inf, inf, inf, inf, inf, inf, inf, inf]

• Step 1: Pop (0, 0). Look at neighbors of 0 (say, nodes 1 and 3).
  • To reach 1 from 0: current_dist (0) + 1 = 1. Since 1 < infinity, update dist[1] = 1 and push (1, 1) into queue.
  • To reach 3 from 0: 0 + 1 = 1. Update dist[3] = 1 and push (3, 1) into queue.
• Step 2: Pop (1, 1). Look at neighbors of 1 (nodes 0, 2, 3).
  • Neighbor 0: distance would be 1 + 1 = 2. But dist[0] = 0 (shorter), so discard.
  • Neighbor 2: distance would be 1 + 1 = 2. Since 2 < infinity, update dist[2] = 2 and push (2, 2).
  • Neighbor 3: distance would be 1 + 1 = 2. But dist[3] = 1 (shorter), so discard.
• Step 3: Process subsequent queue elements (3, 2, 4, 5, 6, 7, 8), continuously checking if dist[node] + 1 < dist[neighbor]. If true, update the distance array and push the neighbor into the queue.

5. Implementation (C++ and Java)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

vector<int> shortestPath(vector<vector<int>>& edges, int N, int M, int src) {
    // 1. Create adjacency list for undirected graph
    vector<vector<int>> adj(N);
    for (auto& edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
    }
    
    // 2. Initialize distance array with a large value (infinity)
    int inf = 1e9;
    vector<int> dist(N, inf);
    
    // 3. Queue for BFS storing nodes
    queue<int> q;
    
    // Configure source
    dist[src] = 0;
    q.push(src);
    
    // 4. Standard BFS Traversal
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : adj[node]) {
            // Check if a shorter path is found
            if (dist[node] + 1 < dist[neighbor]) {
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
            }
        }
    }
    
    // 5. Format output: convert unreachable nodes (inf) to -1
    vector<int> ans(N, -1);
    for (int i = 0; i < N; i++) {
        if (dist[i] != inf) {
            ans[i] = dist[i];
        }
    }
    
    return ans;
}

Java Implementation

import java.util.*;

class Solution {
    public int[] shortestPath(int[][] edges, int n, int m, int src) {
        // 1. Create adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            adj.get(edges[i][0]).add(edges[i][1]);
            adj.get(edges[i][1]).add(edges[i][0]);
        }
        
        // 2. Initialize distance array with infinity
        int inf = (int)1e9;
        int[] dist = new int[n];
        Arrays.fill(dist, inf);
        
        // 3. Queue for BFS
        Queue<Integer> q = new LinkedList<>();
        
        dist[src] = 0;
        q.add(src);
        
        // 4. BFS Traversal
        while (!q.isEmpty()) {
            int node = q.poll();
            
            for (int neighbor : adj.get(node)) {
                if (dist[node] + 1 < dist[neighbor]) {
                    dist[neighbor] = dist[node] + 1;
                    q.add(neighbor);
                }
            }
        }
        
        // 5. Format output: convert unreachable nodes to -1
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (dist[i] != inf) {
                ans[i] = dist[i];
            } else {
                ans[i] = -1;
            }
        }
        
        return ans;
    }
}

6. Real-World Practical Pitfalls & Edge Cases

• Unreachable Components: If the graph has disconnected components, nodes residing outside the source's component will retain their initial infinity value. Failing to map these to -1 will result in incorrect output validation.
• Self-Loops & Multi-Edges: In undirected graph representations, self-loops (node -> node) and parallel edges can be safely encountered. The condition dist[node] + 1 < dist[neighbor] naturally guards against redundant updates, making the algorithm robust against cyclic loops.
• Graph Indexing: Ensure whether the graph is 0-indexed or 1-indexed before allocating the size of the distance and answer arrays.

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(V + 2E)$
  • Visiting every vertex takes $\mathcal{O}(V)$ time.
  • Traversing all edges across both directions in the adjacency list takes $\mathcal{O}(2E)$ time.
• Space Complexity: $\mathcal{O}(V + E)$
  • Adjacency list storage requires $\mathcal{O}(V + 2E)$ space.
  • The distance array and queue require $\mathcal{O}(V)$ auxiliary space.

8. Summary and Key Takeaways

• Uniform Weight Advantage: When all edge weights are equal to 1, shortest path problems can be solved in linear time without Dijkstra's priority queue.
• Implicit Queue Ordering: A standard FIFO queue naturally maintains distance levels because items enter and leave in strictly increasing order of distance steps (+1).
• Distance Array over Visited Set: Maintaining a dist array initialized to infinity serves a dual purpose: it tracks whether a node has been reached and records its minimum distance simultaneously.
• Unreachable Node Handling: Any node whose distance value remains at infinity after the BFS completes must be translated to -1.
• Optimal Efficiency: The algorithm runs in standard BFS time ($\mathcal{O}(V + 2E)$), making it optimal for unweighted or unit-weight graph shortest path queries.