Shortest paths (Dijkstra, Bellman-Ford, 0-1 BFS)

intermediateCommon atGoogleMetaAmazonUbertrading firmsRead firstBreadth-first searchHeapsGraph representationPractise in the Sandbox →

All shortest-path algorithms repeat one move, relaxation: if going through u makes v cheaper, update dist[v]. They differ in the order they relax edges. Dijkstra settles nodes cheapest-first with a min-heap, O((V + E) log V), but needs non-negative weights. Bellman-Ford relaxes every edge V − 1 times, O(V·E), handles negative weights and detects negative cycles. 0-1 BFS uses a deque for weights 0 and 1, O(V + E).

The idea in plain words

Plain BFS finds the fewest hops. Once edges have costs (minutes, dollars, metres), a 3-hop route can beat a 1-hop one. We need to explore by cost, not by hop count.

Relaxation is the only update any of these algorithms makes:

if dist[u] + w(u, v) < dist[v]:
    dist[v] = dist[u] + w(u, v)
    parent[v] = u

Each relaxation can only lower dist[v], and dist[v] is always the cost of some real path. The question is how to order relaxations so you reach the true minimum quickly.

• Dijkstra’s insight: among unsettled nodes, the one with the smallest tentative distance is already final. Any other route to it would leave the settled region through a node that’s at least as far, and with non-negative edges, the rest of the detour can’t make it cheaper. So settle it and relax its edges. A min-heap finds that node fast.
• Bellman-Ford’s insight: a shortest path (without a negative cycle) has at most V − 1 edges. Relaxing every edge once extends every correct prefix by at least one edge. So V − 1 full passes are enough. If a V-th pass still improves something, a negative cycle is reachable and “shortest” is undefined.

See it

Edit the edges (a-b 4 is two-way, a>b 4 is one-way), pick the source and the algorithm, and step through. The badge under each node is its current distance. With Dijkstra, watch the heap: an improved node gets a second entry, and the old one is popped later as a stale entry and skipped.

Settle the closest node, relax its edges

edit the graph, then step

edges: a-b 4 (two-way) or a>b 4 (one-way)

RoadsNegative edgeNegative cycle

abcdefdist0∞∞∞∞∞via······

min-heap (smallest first)

(0, a)

settled0/6

pops0

pushes1

settled / shortest-path treein the heapcurrent / improveddistance just droppedwrong answer (negative edge)stale heap entry

dist(a) = 0, everything else ∞. The min-heap holds (distance, node) candidates; the smallest is always safe to settle.

↺◀▶ Play▶1 / 21

Try these:

• Negative edge with Dijkstra: c gets settled at 2 before the route through b (5 − 4 = 1) is seen. The final frame flags the wrong answers. Switch to Bellman-Ford to get them right.
• Negative cycle: Bellman-Ford’s check pass still finds an improvement and highlights the cycle b → d → c → b (2 − 4 + 1 = −1).

When to reach for it

The problem says…	Use	Why
fewest steps, all moves cost the same	BFS	Hop count is the cost. O(V + E).
weighted, all weights ≥ 0 (“time”, “distance”, “price”)	Dijkstra	Fastest general-purpose choice.
weights can be negative, or “detect a loop that keeps getting cheaper”	Bellman-Ford	Handles negatives; detects negative cycles.
weights are only 0 or 1 (“free moves vs paid moves”, “turn costs 1”)	0-1 BFS	Linear time, no heap.
a DAG (no cycles), any weights	relax in topological order	One pass, O(V + E).
all pairs, V ≤ ~400	Floyd-Warshall	O(V³), three nested loops, tiny code.

How it works

Dijkstra (lazy deletion)

1. Set dist[src] = 0, everything else ∞. Push (0, src) on a min-heap.
2. Pop the smallest (d, u). If d > dist[u], it’s a stale entry: skip it.
3. Otherwise u is settled. Relax each edge u → v.
4. When dist[v] improves, push (dist[v], v). Don’t try to update the old entry; it’ll be skipped in step 2.

Python

dijkstra.py

import heapq
import math


def dijkstra(n: int, adj: list[list[tuple[int, int]]], src: int) -> list[float]:
    """Cheapest cost from src to every node. adj[u] = [(v, w), ...] with w >= 0."""
    dist = [math.inf] * n
    dist[src] = 0
    heap = [(0, src)]                       # 1. (distance, node); heapq is a min-heap
    while heap:
        d, u = heapq.heappop(heap)          # 2. closest unsettled candidate
        if d > dist[u]:                     #    stale entry: u was already settled cheaper
            continue
        for v, w in adj[u]:                 # 3. relax every edge out of u
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))  # 4. push instead of decrease-key
    return dist


if __name__ == "__main__":
    edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 5), (2, 3, 8), (3, 4, 3)]
    adj: list[list[tuple[int, int]]] = [[] for _ in range(6)]
    for a, b, w in edges:
        adj[a].append((b, w))
        adj[b].append((a, w))               # undirected for this demo
    assert dijkstra(6, adj, 0) == [0, 3, 2, 8, 11, math.inf]  # node 5 is unreachable
    print("ok")

TypeScript

dijkstra.ts

import assert from "node:assert/strict";

/** Minimal binary min-heap of [priority, value] pairs: JS has no built-in priority queue. */
class MinHeap {
  private a: [number, number][] = [];
  get size() { return this.a.length; }
  push(x: [number, number]) {
    const a = this.a; a.push(x);
    for (let i = a.length - 1, p; i > 0 && a[(p = (i - 1) >> 1)][0] > a[i][0]; i = p) [a[i], a[p]] = [a[p], a[i]];
  }
  pop(): [number, number] {
    const a = this.a, top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last;
      for (let i = 0; ;) {
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

/** Cheapest cost from src to every node. adj[u] = [[v, w], ...] with w >= 0. */
export function dijkstra(n: number, adj: [number, number][][], src: number): number[] {
  const dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  const heap = new MinHeap(); // 1. (distance, node)
  heap.push([0, src]);
  while (heap.size > 0) {
    const [d, u] = heap.pop(); // 2. closest unsettled candidate
    if (d > dist[u]) continue; //    stale entry: u was already settled cheaper
    for (const [v, w] of adj[u]) { // 3. relax every edge out of u
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]); // 4. push instead of decrease-key
      }
    }
  }
  return dist;
}

const adj: [number, number][][] = Array.from({ length: 6 }, () => []);
for (const [a, b, w] of [[0, 1, 4], [0, 2, 2], [2, 1, 1], [1, 3, 5], [2, 3, 8], [3, 4, 3]]) {
  adj[a].push([b, w]); adj[b].push([a, w]); // undirected for this demo
}
assert.deepEqual(dijkstra(6, adj, 0), [0, 3, 2, 8, 11, Infinity]); // node 5 is unreachable
console.log("ok");

C#

dijkstra.cs

var adj = Enumerable.Range(0, 6).Select(_ => new List<(int To, int W)>()).ToArray();
foreach (var (a, b, w) in new[] { (0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 5), (2, 3, 8), (3, 4, 3) })
{
    adj[a].Add((b, w)); adj[b].Add((a, w)); // undirected for this demo
}
var dist = Dijkstra(6, adj, 0);
if (string.Join(",", dist) != $"0,3,2,8,11,{long.MaxValue}") throw new Exception(string.Join(",", dist));
Console.WriteLine("ok");

// Cheapest cost from src to every node; long.MaxValue = unreachable. Weights must be >= 0.
static long[] Dijkstra(int n, List<(int To, int W)>[] adj, int src)
{
    var dist = Enumerable.Repeat(long.MaxValue, n).ToArray();
    dist[src] = 0;
    var heap = new PriorityQueue<int, long>();        // 1. element = node, priority = distance
    heap.Enqueue(src, 0);
    while (heap.TryDequeue(out var u, out var d))     // 2. closest unsettled candidate
    {
        if (d > dist[u]) continue;                    //    stale entry: u was settled cheaper
        foreach (var (v, w) in adj[u])                // 3. relax every edge out of u
        {
            if (d + w < dist[v])
            {
                dist[v] = d + w;
                heap.Enqueue(v, dist[v]);             // 4. no decrease-key: push a new entry
            }
        }
    }
    return dist;
}

Heaps in each language

Python’s heapq is a min-heap over a plain list; push tuples (dist, node). .NET 6+ has PriorityQueue<TElement, TPriority>, also a min-heap, without decrease-key. TypeScript and JavaScript have no built-in heap: write a 25-line binary heap (as above) or, in an interview, say you’d use one and keep going.

Bellman-Ford

1. Set dist[src] = 0, everything else ∞.
2. Repeat V − 1 times: relax every edge. Stop early if a pass changes nothing.
3. Run one more pass. If any edge still relaxes, a negative cycle is reachable from the source.

Python

bellman_ford.py

import math


def bellman_ford(n: int, edges: list[tuple[int, int, int]], src: int) -> list[float] | None:
    """Shortest distances allowing negative weights. None if a negative cycle is reachable."""
    dist = [math.inf] * n
    dist[src] = 0
    for _ in range(n - 1):                  # 1. a shortest path has at most n-1 edges
        changed = False
        for u, v, w in edges:               # 2. relax every edge, in any order
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:                     #    nothing moved: already final
            break
    for u, v, w in edges:                   # 3. one more pass: any improvement means
        if dist[u] + w < dist[v]:           #    a negative cycle is reachable
            return None
    return dist


if __name__ == "__main__":
    # 0->1 costs 5, but 0->2->1 costs 2 + (-4) = -2: a negative edge Dijkstra would miss.
    assert bellman_ford(4, [(0, 1, 5), (0, 2, 2), (2, 1, -4), (1, 3, 1)], 0) == [0, -2, 2, -1]
    # 1 -> 2 -> 1 sums to -1: a negative cycle.
    assert bellman_ford(3, [(0, 1, 1), (1, 2, 2), (2, 1, -3)], 0) is None
    assert bellman_ford(2, [], 0) == [0, math.inf]
    print("ok")

TypeScript

bellman_ford.ts

import assert from "node:assert/strict";

/** Shortest distances allowing negative weights. null if a negative cycle is reachable. */
export function bellmanFord(n: number, edges: [number, number, number][], src: number): number[] | null {
  const dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  for (let pass = 0; pass < n - 1; pass++) { // 1. a shortest path has at most n-1 edges
    let changed = false;
    for (const [u, v, w] of edges) { // 2. relax every edge, in any order
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }
    if (!changed) break; // nothing moved: already final
  }
  for (const [u, v, w] of edges) { // 3. one more pass: any improvement means
    if (dist[u] + w < dist[v]) return null; // a negative cycle is reachable
  }
  return dist;
}

// 0->1 costs 5, but 0->2->1 costs 2 + (-4) = -2: a negative edge Dijkstra would miss.
assert.deepEqual(bellmanFord(4, [[0, 1, 5], [0, 2, 2], [2, 1, -4], [1, 3, 1]], 0), [0, -2, 2, -1]);
// 1 -> 2 -> 1 sums to -1: a negative cycle.
assert.equal(bellmanFord(3, [[0, 1, 1], [1, 2, 2], [2, 1, -3]], 0), null);
assert.deepEqual(bellmanFord(2, [], 0), [0, Infinity]);
console.log("ok");

C#

bellman_ford.cs

// 0->1 costs 5, but 0->2->1 costs 2 + (-4) = -2: a negative edge Dijkstra would miss.
var d = BellmanFord(4, [(0, 1, 5), (0, 2, 2), (2, 1, -4), (1, 3, 1)], 0);
if (d is null || string.Join(",", d) != "0,-2,2,-1") throw new Exception("distances");
// 1 -> 2 -> 1 sums to -1: a negative cycle.
if (BellmanFord(3, [(0, 1, 1), (1, 2, 2), (2, 1, -3)], 0) is not null) throw new Exception("cycle");
Console.WriteLine("ok");

// Shortest distances allowing negative weights. null if a negative cycle is reachable.
static double[]? BellmanFord(int n, (int U, int V, int W)[] edges, int src)
{
    var dist = Enumerable.Repeat(double.PositiveInfinity, n).ToArray();
    dist[src] = 0;
    for (int pass = 0; pass < n - 1; pass++)          // 1. a shortest path has at most n-1 edges
    {
        bool changed = false;
        foreach (var (u, v, w) in edges)              // 2. relax every edge, in any order
        {
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
        }
        if (!changed) break;                          //    nothing moved: already final
    }
    foreach (var (u, v, w) in edges)                  // 3. one more pass: any improvement means
        if (dist[u] + w < dist[v]) return null;       //    a negative cycle is reachable
    return dist;
}

0-1 BFS

1. Use a deque. Start with src at distance 0.
2. Pop from the front: it always has the smallest distance in the deque.
3. Relax edges. A 0-weight improvement goes on the front (same distance), a 1-weight one on the back (next distance).

Python

zero_one_bfs.py

from collections import deque
import math


def zero_one_bfs(n: int, adj: list[list[tuple[int, int]]], src: int) -> list[float]:
    """Shortest paths when every weight is 0 or 1, in O(V + E) with a deque."""
    dist = [math.inf] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()                    # 1. front holds the smallest distance
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)        # 2. free edge: same distance, goes first
                else:
                    dq.append(v)            # 3. cost-1 edge: next layer, goes last
    return dist


if __name__ == "__main__":
    # 0 -1- 1 -1- 2 -1- 3, plus a free shortcut 0 -0- 2.
    adj: list[list[tuple[int, int]]] = [[] for _ in range(4)]
    for a, b, w in [(0, 1, 1), (1, 2, 1), (2, 3, 1), (0, 2, 0)]:
        adj[a].append((b, w))
        adj[b].append((a, w))
    assert zero_one_bfs(4, adj, 0) == [0, 1, 0, 1]
    print("ok")

TypeScript

zero_one_bfs.ts

import assert from "node:assert/strict";

/** Shortest paths when every weight is 0 or 1, in O(V + E) with a deque. */
export function zeroOneBfs(n: number, adj: [number, 0 | 1][][], src: number): number[] {
  const dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  // JS has no deque: two stacks act as one. front is reversed, so its end is the head.
  let front: number[] = [src];
  let back: number[] = [];
  while (front.length || back.length) {
    if (!front.length) { front = back.reverse(); back = []; }
    const u = front.pop()!; // 1. head holds the smallest distance
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        if (w === 0) front.push(v); // 2. free edge: same distance, goes first
        else back.push(v); // 3. cost-1 edge: next layer, goes last
      }
    }
  }
  return dist;
}

// 0 -1- 1 -1- 2 -1- 3, plus a free shortcut 0 -0- 2.
const adj: [number, 0 | 1][][] = [[], [], [], []];
for (const [a, b, w] of [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 2, 0]] as [number, number, 0 | 1][]) {
  adj[a].push([b, w]); adj[b].push([a, w]);
}
assert.deepEqual(zeroOneBfs(4, adj, 0), [0, 1, 0, 1]);
console.log("ok");

C#

zero_one_bfs.cs

// 0 -1- 1 -1- 2 -1- 3, plus a free shortcut 0 -0- 2.
var adj = Enumerable.Range(0, 4).Select(_ => new List<(int To, int W)>()).ToArray();
foreach (var (a, b, w) in new[] { (0, 1, 1), (1, 2, 1), (2, 3, 1), (0, 2, 0) })
{
    adj[a].Add((b, w)); adj[b].Add((a, w));
}
if (string.Join(",", ZeroOneBfs(4, adj, 0)) != "0,1,0,1") throw new Exception("distances");
Console.WriteLine("ok");

// Shortest paths when every weight is 0 or 1, in O(V + E) with a deque.
static int[] ZeroOneBfs(int n, List<(int To, int W)>[] adj, int src)
{
    var dist = Enumerable.Repeat(int.MaxValue, n).ToArray();
    dist[src] = 0;
    var dq = new LinkedList<int>();                    // .NET has no Deque<T>; LinkedList is O(1) at both ends
    dq.AddFirst(src);
    while (dq.Count > 0)
    {
        var u = dq.First!.Value; dq.RemoveFirst();     // 1. front holds the smallest distance
        foreach (var (v, w) in adj[u])
        {
            if (dist[u] + w >= dist[v]) continue;
            dist[v] = dist[u] + w;
            if (w == 0) dq.AddFirst(v);                // 2. free edge: same distance, goes first
            else dq.AddLast(v);                        // 3. cost-1 edge: next layer, goes last
        }
    }
    return dist;
}

What it costs

Algorithm	Time	Space	Weights	Negative cycles
BFS	O(V + E)	O(V)	all equal	n/a
0-1 BFS	O(V + E)	O(V)	0 or 1	n/a
Dijkstra, binary heap	O((V + E) log V)	O(V + E) with lazy deletion	≥ 0	can’t handle
Dijkstra, array scan (no heap)	O(V²)	O(V)	≥ 0	can’t handle
Bellman-Ford	O(V·E)	O(V)	any	detects
DAG relaxation in topological order	O(V + E)	O(V)	any	no cycles at all
Floyd-Warshall (all pairs)	O(V³)	O(V²)	any	detects (dist[i][i] < 0)

Why the log in Dijkstra: every successful relaxation pushes one heap entry, so the heap sees at most E pushes and E pops, each O(log E) = O(log V). On a dense graph (E ≈ V²), the O(V²) array version is actually better.

Variations you’ll meet

• Early exit. For a single target, stop when the target is popped (settled), not when it is first pushed.
• Path reconstruction. Store parent[v] on each improvement, then walk back from the target.
• Multi-source. Push every source at distance 0 at the start.
• Grid Dijkstra. Nodes are cells; the cost of entering a cell is the edge weight. Same code with (r, c) tuples.
• Minimax paths (“the route whose worst edge is smallest”). Same Dijkstra skeleton with max(d, w) instead of d + w. Works because max is monotone too.
• State-augmented Dijkstra. When the cost depends on something besides position (fuel left, stops used), the node becomes a tuple. See search over states.
• A*. Dijkstra ordered by dist + h(node), where h is an optimistic estimate of the remaining cost. Same result, fewer nodes explored with a good h.
• SPFA. Bellman-Ford with a queue of “nodes whose distance just changed”. Often fast, same worst case.

Pitfalls

• Dijkstra with negative edges. It can return wrong answers without any error (see the viz).
• “Fixing” Dijkstra for negatives by re-pushing settled nodes. That can work but loses the O((V + E) log V) bound; it can be exponential. Use Bellman-Ford.
• Comparing against stale entries. Without if d > dist[u]: continue, you relax from outdated distances and do extra work.
• Infinity arithmetic. math.inf + w is fine in Python, but int.MaxValue + w overflows in C#. Guard with if dist[u] == INF: continue or use long.
• Undirected input. Add both directions when building the adjacency list.
• Bellman-Ford’s check only finds negative cycles reachable from the source. To find any negative cycle, start with every dist = 0 (a virtual source connected to all nodes).

In the interview

• Ask first: can weights be negative? Zero? Is the graph directed? One target or all? How big are V and E?
• State the choice with its reason: “Weights are non-negative, so Dijkstra with a binary heap: O((V + E) log V).”
• Explain why Dijkstra is correct in one sentence: “When I pop the minimum, every other route has to leave through a node that’s at least as far, and non-negative edges can’t make it shorter.”
• Expected follow-ups: return the path, stop early at the target, what if weights can be negative, add a constraint such as a resource that runs out, or run it on a grid with cell costs.

Check yourself

Check yourself

pick one

Edges have non-negative weights. You pop (7, x) from Dijkstra's heap but dist[x] is already 5. What should you do?

ARelax x's edges again using 7BSkip it: it is a stale entry from before dist[x] improvedCUpdate dist[x] to 7DIt means there is a negative cycle

Check yourself

pick one

Why does Bellman-Ford run exactly V − 1 passes?

ABecause each pass settles one node, like DijkstraBBecause a shortest simple path has at most V − 1 edges, and each pass extends every correct prefix by at least one edgeCIt is an arbitrary safety margin

Check yourself

pick one

A grid where moving straight is free but turning costs 1. Which algorithm is the natural fit?

APlain BFSB0-1 BFS over (cell, direction) statesCBellman-FordDFloyd-Warshall

Practice on your own

These are classic textbook exercises, not gym questions:

• Minimum effort path: a route through a height grid minimising the largest single climb.
• Shortest path in a grid where some cells cost more to enter, from top-left to bottom-right.
• Minimum number of walls to remove to get from one corner of a grid to the other (0-1 BFS).
• Detect whether a directed graph with weighted edges has any negative cycle at all.
• Single-source shortest paths in a weighted DAG with some negative edges, using a topological order.

Go deeper

• CLRS, Introduction to Algorithms, “Single-Source Shortest Paths”: relaxation, Bellman-Ford, DAG shortest paths and Dijkstra, with proofs.
• cp-algorithms: Dijkstra, Bellman-Ford and 0-1 BFS.
• Sedgewick and Wayne, Algorithms 4.4: Shortest paths.
• Python heapq and .NET PriorityQueue<TElement,TPriority> reference docs.

Related

Breadth-first searchThe unweighted special case.

HeapsThe priority queue behind Dijkstra.

Search over statesWhen the node is (position, extra state).

Minimum spanning treesPrim's algorithm looks like Dijkstra but answers a different question.