Shortest Path (Unweighted) - Learning Module

Loading content...

0/276

The Distance Array

Tracking Distance from the Source

While parent tracking enables us to reconstruct paths, the distance array provides something equally valuable: the shortest distance from the source to every reachable vertex. This is often exactly what we need—and sometimes it's more useful than the path itself.

The distance array is conceptually simple: distance[v] stores the shortest distance from the source to vertex v. But this simple structure unlocks powerful capabilities: constant-time distance queries, distance-based filtering, and serves as the conceptual foundation for weighted shortest path algorithms like Dijkstra's.

What You Will Learn

By the end of this page, you will understand how to initialize and maintain the distance array during BFS, use it for efficient distance queries, combine it with parent tracking for complete path solutions, and recognize how it forms the conceptual bridge to weighted shortest path algorithms.

What Is the Distance Array?

Definition:

The distance array (or distance map) is a data structure that records the shortest distance from a designated source vertex to each vertex in the graph.

distance[v] = d means: "the shortest path from source to v has length d"

Key Properties:

distance[source] = 0 — The distance from any vertex to itself is zero
distance[v] = ∞ (or undefined) — For unreachable vertices, distance is infinite or undefined
Non-negative values — In unweighted graphs, all distances are non-negative integers
Monotonically increasing during BFS — As BFS progresses, we discover vertices at distance 1, then 2, then 3, etc.

Relationship to Parent Array:

The distance array and parent array are complementary:

Aspect	Distance Array	Parent Array
What it stores	Shortest distance from source	Previous vertex on shortest path
Answers	"How far is v from source?"	"How do I get to v?"
Size	O(V)	O(V)
Can compute other	Can compute parent via BFS	Cannot compute distance without BFS

While you can infer distance by counting parent pointers (O(path length) per query), the distance array provides O(1) lookups. Conversely, you cannot reconstruct paths from distances alone—you need parent pointers.

Implementation Choice: Array vs Map

For vertices numbered 0 to V-1, use an array: distance[i]. For arbitrary vertex identifiers (strings, objects, tuples), use a Map: distance.get(vertex). The array approach is slightly faster but requires contiguous integer vertices.

Computing the Distance Array

The distance array is computed alongside BFS traversal. The key insight: when we discover a vertex v from vertex u, we know distance[v] = distance[u] + 1.

Algorithm:

Initialize distance[source] = 0; all other distances undefined (or ∞)
Mark source as visited and enqueue
For each dequeued vertex u:
- For each unvisited neighbor v:
  - Set distance[v] = distance[u] + 1
  - Mark v visited and enqueue
After BFS completes, distance[v] contains shortest distance for all reachable v

bfs_distance_array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
function computeDistances(
    graph: Map<number, number[]>,
    source: number
): Map<number, number> {
    const distance = new Map<number, number>();
    const queue: number[] = [];
    
    // Initialize source
    distance.set(source, 0);
    queue.push(source);
    
    while (queue.length > 0) {
        const current = queue.shift()!;
        const currentDist = distance.get(current)!;
        
        for (const neighbor of graph.get(current) || []) {
            if (!distance.has(neighbor)) {
                // First time seeing this neighbor
                distance.set(neighbor, currentDist + 1);
                queue.push(neighbor);
            }
        }
    }
    
    return distance;
}
 
// Usage example
const graph = new Map([
    [0, [1, 2]],
    [1, [0, 3, 4]],
    [2, [0, 4]],
    [3, [1, 5]],
    [4, [1, 2, 5]],
    [5, [3, 4]]
]);
 
const distances = computeDistances(graph, 0);
// distances.get(0) = 0  (source)
// distances.get(1) = 1  (neighbor of 0)
// distances.get(2) = 1  (neighbor of 0)
// distances.get(3) = 2  (neighbor of 1)
// distances.get(4) = 2  (neighbor of 1 or 2)
// distances.get(5) = 3  (neighbor of 3 or 4)

Distance Array Replaces Visited Set

Notice we don't use a separate 'visited' set. The distance map itself serves as the visited tracker: if distance.has(v) is true, vertex v has been visited. This is a common optimization that reduces memory and simplifies code.

Distance Array Invariants

Understanding the invariants (properties that always hold) of the distance array deepens our understanding and helps us reason about correctness.

Key Invariants

•Monotonic Discovery: During BFS, vertices are discovered in non-decreasing order of distance. If we're currently processing vertices at distance d, all newly discovered vertices are at distance d+1.
•First Discovery is Final: Once distance[v] is set, it's never changed. The first path found is the shortest.
•Queue Distance Property: At any point during BFS, the queue contains vertices at at most two consecutive distance levels (d and d+1).
•Triangle Inequality Holds: For any edge (u, v), |distance[u] - distance[v]| ≤ 1. Adjacent vertices differ in distance by at most 1.
•Path Existence: distance[v] is defined if and only if there exists a path from source to v.

Why These Invariants Matter:

Invariant 1 (Monotonic Discovery) is why BFS works for shortest paths. We exhaust closer vertices before discovering farther ones.

Invariant 2 (First Discovery is Final) is why we don't need relaxation (unlike Dijkstra's). We never find a shorter path later.

Invariant 3 (Queue Distance Property) explains the memory efficiency. The queue never holds vertices from wildly different distances.

Invariant 4 (Triangle Inequality) is a structural property of shortest path distances. If two vertices are adjacent, their distances from any third vertex differ by at most 1.

Invariant 5 (Path Existence) lets us use the distance array to check reachability: distance.has(v) === isReachable(v).

Dijkstra's Relaxation

In weighted graphs with Dijkstra's algorithm, distances CAN be improved after first discovery (called 'relaxation'). This is why Dijkstra's needs a priority queue—to always process the vertex with the smallest tentative distance. BFS's simplicity comes from the fact that all edges have equal weight, eliminating the need for relaxation.

Applications of the Distance Array

The distance array enables a variety of useful queries and computations beyond simple shortest paths.

Common Distance Array Applications
Application	How Distance Array Helps	Complexity
Shortest path length query	distance.get(target) gives the answer directly	O(1) after O(V+E) BFS
Reachability check	distance.has(v) indicates if v is reachable	O(1) per query
Find all vertices at distance k	Filter: vertices where distance[v] === k	O(V)
Graph eccentricity from source	max(distance.values()) gives the maximum distance	O(V)
Level-order listing	Group vertices by their distance values	O(V)
Distance-based filtering	Select vertices within a distance threshold	O(V)

Example: Finding All Vertices at Exactly Distance K

vertices_at_distance_k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function verticesAtDistanceK(
    graph: Map<number, number[]>,
    source: number,
    k: number
): number[] {
    const distance = new Map<number, number>();
    const queue: number[] = [];
    
    distance.set(source, 0);
    queue.push(source);
    
    while (queue.length > 0) {
        const current = queue.shift()!;
        const currentDist = distance.get(current)!;
        
        // Optimization: stop BFS once we've processed all vertices at distance k
        if (currentDist > k) break;
        
        for (const neighbor of graph.get(current) || []) {
            if (!distance.has(neighbor)) {
                distance.set(neighbor, currentDist + 1);
                queue.push(neighbor);
            }
        }
    }
    
    // Filter vertices at exactly distance k
    const result: number[] = [];
    for (const [vertex, dist] of distance) {
        if (dist === k) result.push(vertex);
    }
    return result;
}
 
// Example: Find all vertices exactly 2 hops from vertex 0
// const atDistance2 = verticesAtDistanceK(graph, 0, 2);

Early Termination

When we only need vertices up to distance k, we can terminate BFS early once we've finished processing the k-th level. Since BFS processes levels in order, once we see a vertex at distance > k, all remaining queue entries are at distance ≥ k, so we can stop.

Multi-Source BFS

A powerful extension of BFS computes the distance from multiple sources simultaneously. Instead of starting from a single source, we start from a set of sources. The distance array then stores the distance to the nearest source.

Use Cases:

Distance to nearest exit in a maze with multiple exits
Distance to nearest hospital/fire station
Flood fill from multiple seed points
Finding vertices equidistant from two sets of sources

multi_source_bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function multiSourceBFS(
    graph: Map<number, number[]>,
    sources: number[]
): Map<number, number> {
    const distance = new Map<number, number>();
    const queue: number[] = [];
    
    // Initialize ALL sources at distance 0
    for (const source of sources) {
        distance.set(source, 0);
        queue.push(source);
    }
    
    // Standard BFS from here
    while (queue.length > 0) {
        const current = queue.shift()!;
        const currentDist = distance.get(current)!;
        
        for (const neighbor of graph.get(current) || []) {
            if (!distance.has(neighbor)) {
                distance.set(neighbor, currentDist + 1);
                queue.push(neighbor);
            }
        }
    }
    
    return distance;
    // distance[v] = distance to nearest source
}
 
// Example: Given a maze with multiple exits at positions [5, 12, 18],
// find the distance from every cell to the nearest exit
// const distToNearestExit = multiSourceBFS(mazeGraph, [5, 12, 18]);

Why This Works:

By initializing all sources at distance 0 and adding them all to the initial queue, BFS explores outward from all sources simultaneously. The first time a vertex is discovered, it's discovered from the nearest source (by the level-order property). This is equivalent to adding a "super-source" vertex connected to all real sources with zero-weight edges.

Complexity:

Multi-source BFS has the same time complexity as single-source BFS: O(V + E). We still visit each vertex once and explore each edge once. The only difference is the initialization.

Tracking Which Source

Sometimes you need to know not just the distance to the nearest source, but WHICH source is nearest. Maintain a parallel 'nearestSource' array: when discovering vertex v from current, set nearestSource[v] = nearestSource[current]. For sources, nearestSource[source] = source.

Combining Distance and Parent Arrays

For complete shortest path solutions, we often maintain both arrays simultaneously. This provides both O(1) distance queries and path reconstruction capability.

complete_bfs
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
interface BFSResult {
    distance: Map<number, number>;
    parent: Map<number, number | null>;
}
 
function completeBFS(
    graph: Map<number, number[]>,
    source: number
): BFSResult {
    const distance = new Map<number, number>();
    const parent = new Map<number, number | null>();
    const queue: number[] = [];
    
    // Initialize source
    distance.set(source, 0);
    parent.set(source, null);
    queue.push(source);
    
    while (queue.length > 0) {
        const current = queue.shift()!;
        const currentDist = distance.get(current)!;
        
        for (const neighbor of graph.get(current) || []) {
            if (!distance.has(neighbor)) {
                distance.set(neighbor, currentDist + 1);
                parent.set(neighbor, current);
                queue.push(neighbor);
            }
        }
    }
    
    return { distance, parent };
}
 
// Usage
function shortestPath(
    graph: Map<number, number[]>,
    source: number,
    target: number
): { path: number[] | null; distance: number } {
    const { distance, parent } = completeBFS(graph, source);
    
    if (!distance.has(target)) {
        return { path: null, distance: -1 };
    }
    
    // Reconstruct path
    const path: number[] = [];
    let current: number | null = target;
    while (current !== null) {
        path.push(current);
        current = parent.get(current) ?? null;
    }
    
    return { 
        path: path.reverse(), 
        distance: distance.get(target)! 
    };
}

Design Considerations:

When to use distance array only:

You only need to know how far, not how to get there
You're computing graph metrics (eccentricity, radius, diameter)
Memory is constrained and you don't need paths

When to use parent array only:

You only need the path, distance can be computed from path length
You're implementing path-following behavior (like AI navigation)

When to use both:

You need both distance queries and path reconstruction
Different parts of your application need different information
You want to verify correctness (path length should equal stored distance)

Grid-Specific Distance Patterns

Grids are so common that they deserve special attention. Here are patterns specific to grid-based distance computation.

grid_distance_bfs
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
type Point = [number, number];
 
// 4-directional movement
const DIRS_4: Point[] = [[0, 1], [0, -1], [1, 0], [-1, 0]];
 
// 8-directional movement (includes diagonals)
const DIRS_8: Point[] = [
    [0, 1], [0, -1], [1, 0], [-1, 0],
    [1, 1], [1, -1], [-1, 1], [-1, -1]
];
 
function gridDistanceBFS(
    grid: number[][],
    startRow: number,
    startCol: number,
    directions: Point[] = DIRS_4
): number[][] {
    const rows = grid.length;
    const cols = grid[0].length;
    
    // Initialize distance grid with -1 (unreachable)
    const distance: number[][] = Array.from(
        { length: rows },
        () => Array(cols).fill(-1)
    );
    
    const queue: Point[] = [];
    
    // Start from source
    distance[startRow][startCol] = 0;
    queue.push([startRow, startCol]);
    
    while (queue.length > 0) {
        const [r, c] = queue.shift()!;
        const currentDist = distance[r][c];
        
        for (const [dr, dc] of directions) {
            const nr = r + dr;
            const nc = c + dc;
            
            // Check bounds
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            
            // Check if passable (0 = passable, 1 = wall)
            if (grid[nr][nc] === 1) continue;
            
            // Check if already visited
            if (distance[nr][nc] !== -1) continue;
            
            distance[nr][nc] = currentDist + 1;
            queue.push([nr, nc]);
        }
    }
    
    return distance;
}
 
// Example: Find distance from top-left corner to all reachable cells
/*
const maze = [
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 0]
];
const distances = gridDistanceBFS(maze, 0, 0);
// distances[3][3] = 6 (shortest path length to bottom-right)
*/

Manhattan Distance vs BFS Distance:

In an obstacle-free grid with 4-directional movement, the BFS distance equals the Manhattan distance: |row₁ - row₂| + |col₁ - col₂|. But with obstacles, walls, or special movement rules, BFS computes the true shortest path distance around obstacles.

Visualization of Distance Array on Grid:

Grid:           Distance from (0,0):
. . # .         0  1  #  7
. . . .         1  2  3  6
# . # .         #  3  #  5
. . . .         5  4  5  4

The distance array provides a "heat map" of distances from the source, useful for:

Pathfinding AI (move toward decreasing distance)
Effects that spread outward (fire, flood)
Visualization of accessibility

Bidirectional BFS with Distance Arrays

For finding the shortest path between two specific vertices, bidirectional BFS can be significantly faster than standard BFS. It runs BFS from both source and target simultaneously, meeting in the middle.

Why Bidirectional BFS is Faster:

Suppose the shortest path has length d, and the average branching factor is b.

Standard BFS explores O(b^d) vertices
Bidirectional BFS explores O(2 × b^(d/2)) = O(b^(d/2)) vertices

This is exponentially better for large d.

Example: If b = 10 and d = 6:

Standard BFS: 10^6 = 1,000,000 vertices
Bidirectional BFS: 2 × 10^3 = 2,000 vertices

Implementation Idea:

Maintain two distance arrays: distFromSource and distFromTarget
Alternate BFS steps from each side
When a vertex is visited by both BFSs, compute total distance
Return minimum total distance found

bidirectional_bfs
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function bidirectionalBFS(
    graph: Map<number, number[]>,
    source: number,
    target: number
): number {
    if (source === target) return 0;
    
    // Distance from source (forward search)
    const distS = new Map<number, number>();
    const queueS: number[] = [];
    distS.set(source, 0);
    queueS.push(source);
    
    // Distance from target (backward search)
    const distT = new Map<number, number>();
    const queueT: number[] = [];
    distT.set(target, 0);
    queueT.push(target);
    
    let result = Infinity;
    
    while (queueS.length > 0 && queueT.length > 0) {
        // Expand smaller frontier (optimization)
        if (queueS.length <= queueT.length) {
            const current = queueS.shift()!;
            const currentDist = distS.get(current)!;
            
            for (const neighbor of graph.get(current) || []) {
                if (!distS.has(neighbor)) {
                    distS.set(neighbor, currentDist + 1);
                    queueS.push(neighbor);
                    
                    // Check if meets backward search
                    if (distT.has(neighbor)) {
                        result = Math.min(
                            result, 
                            distS.get(neighbor)! + distT.get(neighbor)!
                        );
                    }
                }
            }
        } else {
            const current = queueT.shift()!;
            const currentDist = distT.get(current)!;
            
            for (const neighbor of graph.get(current) || []) {
                if (!distT.has(neighbor)) {
                    distT.set(neighbor, currentDist + 1);
                    queueT.push(neighbor);
                    
                    // Check if meets forward search
                    if (distS.has(neighbor)) {
                        result = Math.min(
                            result, 
                            distS.get(neighbor)! + distT.get(neighbor)!
                        );
                    }
                }
            }
        }
        
        // Early termination: if we found a meeting point
        // and current frontiers can't improve, stop
        if (result !== Infinity) {
            const sLevel = distS.size > 0 ? 
                Math.max(...distS.values()) : Infinity;
            const tLevel = distT.size > 0 ? 
                Math.max(...distT.values()) : Infinity;
            if (sLevel + tLevel >= result) break;
        }
    }
    
    return result === Infinity ? -1 : result;
}

Bidirectional BFS Complexity

Bidirectional BFS requires the graph to be undirected (or you need the reverse graph for backward search). It also requires knowing both source and target upfront. For single-source all-targets queries, standard BFS is still appropriate.

Summary: The Distance Array

Let's consolidate the key concepts about the distance array:

Key Takeaways

•Distance array stores shortest distances — distance[v] is the length of the shortest path from source to v
•Computed incrementally during BFS — distance[v] = distance[parent] + 1
•Serves dual duty as visited set — Presence in distance map indicates visited status
•Enables O(1) distance queries — After O(V+E) BFS, any distance query is instant
•Multi-source BFS — Initialize multiple sources at distance 0 for nearest-source distances
•Combine with parent array — For complete solutions needing both distance and path
•Grid-specific patterns — 2D distance arrays with directional movement
•Bidirectional optimization — Use two distance arrays for faster source-to-target queries

What's Next:

We've covered the mechanics of BFS for shortest paths: the level-order property, parent tracking, and distance arrays. But why does all of this work? The final page provides the deep theoretical justification—why BFS works for unweighted shortest paths—cementing your understanding with rigorous reasoning.

Page Complete

You now have a thorough understanding of the distance array—its purpose, computation, invariants, and applications. Combined with parent tracking from the previous page, you have all the tools needed for complete shortest path solutions in unweighted graphs. The final page provides the theoretical foundation for why these techniques work.