Data Structures & AlgorithmsGraph Algorithms

Shortest Path — Unweighted Graphs (BFS)

LevelIntermediate

Duration75 mins

TopicGraph Algorithms

3 / 4

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] = \infty (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 \infty) 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 \geq 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

3 / 4

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)

Can compute other

Can compute parent via BFS

Cannot compute distance without BFS

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)

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)! }; }

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) */

The Distance Array

Tracking Distance from the Source

What Is the Distance Array?

Computing the Distance Array

Distance Array Invariants

Applications of the Distance Array

Multi-Source BFS

Combining Distance and Parent Arrays

Grid-Specific Distance Patterns

There’s more to understand.

The Distance Array

Tracking Distance from the Source

What Is the Distance Array?

Computing the Distance Array

Distance Array Invariants

Applications of the Distance Array

Multi-Source BFS

Combining Distance and Parent Arrays

Grid-Specific Distance Patterns

There’s more to understand.