Shortest Path

"Dijkstra, Bellman-Ford, Floyd-Warshall, SPFA, 0-1 BFS, A*."

Deep Dive Tutorial

When graph edges have weights, BFS no longer gives shortest paths. You need one of three algorithms: Dijkstra (greedy, non-negative weights), Bellman-Ford (DP, handles negative weights), or Floyd-Warshall (all-pairs DP). The right choice depends on whether negative weights exist, whether you need single-source or all-pairs, and the graph density.

Algorithm	Time	Handles Negatives?	Use When
BFS	O(V+E)	No (unweighted)	All edges weight 1
Dijkstra (heap)	O((V+E) log V)	No	Non-negative weights, single source
Bellman-Ford	O(V·E)	Yes	Negative weights; negative cycle detection
Floyd-Warshall	O(V³)	Yes (no neg cycles)	All pairs, dense graph, V ≤ 500
0-1 BFS	O(V+E)	No	Edge weights only 0 or 1
SPFA	O(V·E) worst	Yes	Faster Bellman-Ford in practice (risky)

Dijkstra's Algorithm

lightbulb

Dijkstra's key insight: Greedily process the unvisited node with the smallest known distance. Since all edge weights ≥ 0, this greedy choice is correct — a node processed from the heap has its final shortest distance.

Min-heap invariant: heap stores (distance, node). Always process the smallest distance first. When we pop a node, if we've already found a shorter path to it, skip it (lazy deletion).

Dijkstra's — single source shortest path with min-heap

// graph[u] = [[v, weight], ...]
function dijkstra(graph, src, n) {
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    // Min-heap: [distance, node]
    // JS doesn't have built-in heap — use sorted array for small n,
    // or implement a binary heap for large n
    const heap = [[0, src]];

    while (heap.length) {
        // Extract minimum (simulate heap with sort for clarity)
        heap.sort((a, b) => a[0] - b[0]);
        const [d, u] = heap.shift();

        if (d > dist[u]) continue;  // stale entry (lazy deletion)

        for (const [v, w] of graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heap.push([dist[v], v]);
            }
        }
    }
    return dist;  // dist[i] = shortest distance from src to i
}

// For competitive programming — minimal heap implementation
class MinHeap {
    constructor() { this.h = []; }
    push(item) {
        this.h.push(item);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            while (true) {
                let s = i, l = 2*i+1, r = 2*i+2;
                if (l < this.h.length && this.h[l][0] < this.h[s][0]) s = l;
                if (r < this.h.length && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
    get size() { return this.h.length; }
}

Bellman-Ford Algorithm

lightbulb

Bellman-Ford key insight: Relax ALL edges V-1 times. After k iterations, dist[v] = shortest path using at most k edges. Since any simple path has at most V-1 edges, V-1 iterations give the true shortest paths.

Negative cycle detection: Do one more (V-th) relaxation. If any distance still improves, a negative cycle exists (you can keep going around it to get shorter and shorter distances).

Bellman-Ford — handles negative weights

// edges = [[u, v, weight], ...]
function bellmanFord(edges, src, n) {
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;

    // Relax all edges n-1 times
    for (let i = 0; i < n - 1; i++) {
        let updated = false;
        for (const [u, v, w] of edges) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // early exit if no update
    }

    // Check for negative cycles (V-th relaxation)
    for (const [u, v, w] of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v])
            return null;  // negative cycle detected
    }

    return dist;
}

Floyd-Warshall (All Pairs)

Floyd-Warshall — all pairs shortest path in O(V³)

function floydWarshall(n, edges) {
    // dist[i][j] = shortest distance from i to j
    const dist = Array.from({length: n}, (_, i) =>
        Array.from({length: n}, (_, j) => i === j ? 0 : Infinity)
    );
    for (const [u, v, w] of edges) {
        dist[u][v] = Math.min(dist[u][v], w);
        // For undirected: dist[v][u] = Math.min(dist[v][u], w);
    }

    // Try every intermediate node k
    for (let k = 0; k < n; k++)
        for (let i = 0; i < n; i++)
            for (let j = 0; j < n; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    // Negative cycle: dist[i][i] < 0 for any i
    return dist;
}

Worked Problems

Network Delay Time

Medium

Solve ↗

Cheapest Flights Within K Stops

Medium

Solve ↗

Path with Minimum Effort

Medium

Solve ↗

Find the City with the Smallest Number of Reachable Threshold

Medium

Solve ↗

Minimum Cost to Reach Destination in Time

Hard

Solve ↗

brain

Shortest path algorithm selection:
- Unweighted graph → BFS (each edge = 1)
- Non-negative weights, single source → Dijkstra with min-heap
- Negative weights / negative cycle detection → Bellman-Ford
- At-most-k edges constraint → Bellman-Ford (k iterations)
- All pairs, small n (≤500) → Floyd-Warshall O(n³)
- Edge weights only 0/1 → 0-1 BFS with deque
- Minimax/maximin path (minimize the maximum edge) → Dijkstra with max instead of sum

← All Patterns