☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Shortest path in undirected graph with unit weights

Hard TUF ID 508 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with n nodes numbered 0 to n - 1 and a list of edges {u, v}. Every edge has length 1. For a given source node src, return an array dist where dist[i] is the length of the shortest path from src to i, that is, the minimum number of edges. If node i cannot be reached, dist[i] is -1.

Constraints: 1 ≤ n ≤ 10^4, 0 ≤ m ≤ 10^4 edges, 0 ≤ src < n.

Example 1

n = 9, src = 0
edges = [0-1, 0-3, 3-4, 4-5, 5-6, 1-2, 2-6, 6-7, 7-8, 6-8]
answer = [0, 1, 2, 1, 2, 3, 3, 4, 4]
// node 6 is 3 away along 0-1-2-6 (and also along 0-3-4-5-6, which is longer)

Example 2

n = 5, src = 0, edges = [0-1, 1-2, 3-4]
answer = [0, 1, 2, -1, -1]   // 3 and 4 are in a different component

Approach 1: Brute force, relax edges until nothing changes

Intuition. Correct distances satisfy one local rule for every edge u - v: dist[v] ≤ dist[u] + 1, because you can always reach v by first reaching u and then taking one more step. So start with dist[src] = 0 and infinity everywhere else, and repair any edge that breaks the rule. Keep sweeping over all edges until a sweep repairs nothing.

How many sweeps are needed? After sweep r, every node whose shortest path uses at most r edges has its correct distance, since the next edge of that path gets repaired in the following sweep. A shortest path never repeats a node, so it uses at most n - 1 edges, and n - 1 sweeps are always enough. In practice we stop as soon as a sweep changes nothing.

Algorithm.

  1. Fill dist with infinity and set dist[src] = 0.
  2. Repeat at most n - 1 times: for each edge, in both directions u → v, if dist[u] is finite and dist[u] + 1 < dist[v], lower dist[v].
  3. Stop early when a sweep changes nothing.
  4. Replace remaining infinities by -1.
static int[] bruteForce(int n, int[][] edges, int src) {
    final int INF = Integer.MAX_VALUE;
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 1; round < n; round++) {             // a shortest path uses at most n - 1 edges
        boolean changed = false;
        for (int[] e : edges) {
            for (int d = 0; d < 2; d++) {                 // undirected: try u -> v and v -> u
                int u = e[d], v = e[1 - d];
                if (dist[u] != INF && dist[u] + 1 < dist[v]) {
                    dist[v] = dist[u] + 1;
                    changed = true;
                }
            }
        }
        if (!changed) break;
    }
    for (int i = 0; i < n; i++) if (dist[i] == INF) dist[i] = -1;
    return dist;
}

Complexity. Time O(V × E): up to V - 1 sweeps over all E edges. Space O(V) for the distance array. This is the Bellman-Ford algorithm specialised to weight 1. It works, but it ignores the most useful fact we have: every edge costs the same.

Intuition. With equal edge lengths, “shortest” just means “fewest edges”, and breadth-first search explores a graph in exactly that order. It processes the source, then all nodes one edge away, then all nodes two edges away, and so on. The queue always holds at most two neighbouring layers, nearer nodes in front of farther ones.

That ordering is why the first time BFS discovers a node is along a shortest path. Suppose v is first discovered from u, so it gets dist[u] + 1. If there were a shorter route to v, its second-to-last node w would be strictly closer to the source than u, so w would have left the queue before u and would have discovered v first. Hence the distance assigned at discovery is final and is never updated, and the distance array can double as the visited array: -1 means “not discovered yet”.

Algorithm.

  1. Build the adjacency list, adding every edge in both directions.
  2. Fill dist with -1, set dist[src] = 0 and enqueue src.
  3. Pop u. For each neighbour v with dist[v] == -1, set dist[v] = dist[u] + 1 and enqueue v.
  4. When the queue is empty, dist is the answer; unreached nodes are still -1.
static int[] optimal(int n, int[][] edges, int src) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int[] dist = new int[n];
    Arrays.fill(dist, -1);                                // -1 also means "not discovered yet"
    dist[src] = 0;
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(src);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.add(v);
            }
        }
    }
    return dist;
}

Dry run on Example 1 from src = 0 (neighbours are visited in the order their edges were listed):

pop newly discovered (distance) queue after
start 0 (0) [0]
0 1 (1), 3 (1) [1, 3]
1 2 (2) [3, 2]
3 4 (2) [2, 4]
2 6 (3) [4, 6]
4 5 (3) [6, 5]
6 7 (4), 8 (4) [5, 7, 8]
5, 7, 8 nothing new []

Node 6 is discovered from 2 with distance 3 before node 5 is even popped, so the longer route 0-3-4-5-6 is never considered. The final array is [0, 1, 2, 1, 2, 3, 3, 4, 4].

Complexity. Time O(V + E): each node is enqueued once and each adjacency list is scanned once (each undirected edge twice). Space O(V + E) for the adjacency list, plus O(V) for the distances and the queue.

Why not DFS, and when BFS stops being enough

DFS finds a path, not the shortest. On the square 0-1-2-3-0, a DFS from 0 may walk 0 → 1 → 2 → 3 and label 3 with distance 3, although the edge 0-3 gives 1. Fixing that requires revisiting nodes whenever a shorter route appears, which loses the linear bound.

BFS relies on every edge having the same length. With arbitrary non-negative weights, the node discovered first is no longer the closest one, and you need Dijkstra’s algorithm, which replaces the FIFO queue with a priority queue. If the graph is directed but still unweighted, the same BFS code works; just add each edge in one direction only.

Edge cases and pitfalls