Algorithms & Coding Interviews · Graphs

Shortest Paths

Which shortest-path algorithm to use depends on the edge weights. Learn when BFS, 0-1 BFS, Dijkstra, Bellman-Ford and Floyd–Warshall apply, why Dijkstra breaks with negative edges, the stale-entry trick, and watch Dijkstra settle a weighted graph and Bellman-Ford respect a stop limit.

🧮 Algorithms & Coding Interviews● Advanced⏱ 16 min read▶ 2 interactive🛠️ 4 exercises

🎯 What you'll learn

Choosing BFS, 0-1 BFS, Dijkstra, Bellman-Ford or Floyd–Warshall
Dijkstra with a min-heap and lazy deletion
Bellman-Ford with a limited number of edges
Six LeetCode problems with animated walkthroughs

📚 Before you start

Part 1The Pattern

"Shortest" depends on the edges. With no weights (every step costs 1), plain BFS is optimal. With non-negative weights, use Dijkstra's algorithm: always expand the closest unfinished node, using a min-heap. With negative weights or a limit on the number of edges, use Bellman-Ford (relax every edge repeatedly). For all pairs on small graphs, Floyd–Warshall. Picking the right one, and explaining why, is most of the interview.

Dijkstra settles nodes in order of distance, relaxing their outgoing edges

1Choosing an Algorithm

Graph	Algorithm	Complexity
unweighted (or all weights equal)	BFS	O(V + E)
weights 0 or 1	0-1 BFS with a deque (0-edges to the front)	O(V + E)
non-negative weights	Dijkstra + min-heap	O((V + E) log V)
negative weights, or "at most k edges/stops"	Bellman-Ford (k + 1 rounds)	O(V · E) or O(k · E)
all pairs, V ≤ ~400	Floyd–Warshall	O(V³)
"minimize the maximum edge on the path"	Dijkstra with `max` instead of `+`, or binary search + BFS, or union-find	O(E log V)

2Dijkstra Template

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function dijkstra(n: number, edges: number[][], src: number): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const heap = new MinHeap<[number, number]>((a, b) => a[0] < b[0]);
  heap.push([0, src]);
  while (heap.size) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]); }
    }
  }
  return dist.map((x) => (x === Infinity ? -1 : x));
}

python

import heapq

def dijkstra(n, edges, src):                    # edges: (u, v, w) with w >= 0, directed
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]                           # (distance, node)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                            # stale entry: a shorter path was found already
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:                    # relax
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return [x if x != float("inf") else -1 for x in dist]

Relaxation: if going through u gives v a shorter distance, update dist[v] and push the new pair. The if d > dist[u]: continue line skips stale heap entries (lazy deletion), which is simpler than a decrease-key operation and is what interviewers expect.

3Why Dijkstra Fails With Negative Edges

Dijkstra assumes that once a node is popped with distance d, nothing can later offer a shorter path, because every remaining path is at least d and adding non-negative edges can't shrink it. A negative edge breaks that guarantee: a longer route through a negative edge can end up shorter than a distance already finalized. Bellman-Ford doesn't finalize anything; it simply relaxes all edges V − 1 times (one more round that still improves something reveals a negative cycle).

4Bellman-Ford With k Stops

To find the cheapest route using at most k + 1 edges, run k + 1 rounds of relaxing every edge, and in each round read distances from a copy of the previous round. That copy ensures each round extends paths by exactly one edge. This is Cheapest Flights Within K Stops.

Under the HoodReal Routing▾

Maps use Dijkstra variants with heuristics: A\* adds an admissible estimate of the remaining distance (straight-line distance) so the search heads toward the goal; production routers (OSRM, Google Maps) precompute contraction hierarchies so continent-scale queries take milliseconds. Network routing protocols are distributed versions: OSPF runs Dijkstra on each router's view of the topology, while RIP is distance-vector, essentially Bellman-Ford.

⚠️ Common Pitfalls

Using Dijkstra with negative edges.
Not skipping stale heap entries, which processes nodes many times (still correct but slow) or, with a naive "visited" check placed wrong, gives wrong answers.
Bellman-Ford without copying the previous round when the number of edges is limited.
Overflow: INF + w in C#/Java int; use long or check before adding.
Using DFS for shortest paths: DFS finds a path, not the shortest.

📋 Quick Reference

text

unweighted → BFS · 0/1 weights → deque · w ≥ 0 → Dijkstra · negatives / ≤k edges → Bellman-Ford
Dijkstra: heap (0, src); pop (d,u); skip if d > dist[u]; relax v: if d+w < dist[v] → update, push
Bellman-Ford k stops: repeat k+1: tmp = dist[:]; for u,v,w: tmp[v] = min(tmp[v], dist[u]+w); dist = tmp

Part 2Interview Problems

Six problems, each needing a different shortest-path tool: Dijkstra, minimax Dijkstra, Bellman-Ford with a stop limit, grid BFS, and Floyd–Warshall.

1Network Delay Time (LeetCode 743)

🟠 Medium. times[i] = (u, v, w): a signal takes w time from node u to v (nodes 1..n). Send a signal from k; return the time for all nodes to receive it, or −1.

text

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 → 2

Approach. Single-source shortest paths with non-negative weights: Dijkstra from k. The answer is the maximum finite distance (−1 if any node is unreachable).

Complexity. O((V + E) log V).

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u].push([v, w]);
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;
  const heap = new MinHeap<[number, number]>((a, b) => a[0] < b[0]);
  heap.push([0, k]);
  while (heap.size) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue;
    for (const [v, w] of adj[u]) if (d + w < dist[v]) { dist[v] = d + w; heap.push([dist[v], v]); }
  }
  const best = Math.max(...dist.slice(1));
  return best === Infinity ? -1 : best;
}

python

import heapq

def network_delay_time(times, n, k):
    adj = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    dist = {k: 0}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

2Path With Minimum Effort (LeetCode 1631)

🟠 Medium. Move through a height grid from top-left to bottom-right. A route's effort is its maximum absolute height difference between consecutive cells. Return the minimum effort.

text

[[1,2,2],[3,8,2],[5,3,5]] → 2

Approach. Dijkstra where the path cost is the max edge so far instead of a sum: cost(v) = max(cost(u), |h[u] − h[v]|). The heap still pops cells in non-decreasing cost order, so the first time the target is popped, its cost is optimal.

Complexity. O(R · C · log(R · C)).

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function minimumEffortPath(heights: number[][]): number {
  const R = heights.length, C = heights[0].length;
  const best = Array.from({ length: R }, () => new Array(C).fill(Infinity));
  best[0][0] = 0;
  const heap = new MinHeap<[number, number, number]>((a, b) => a[0] < b[0]);
  heap.push([0, 0, 0]);
  while (heap.size) {
    const [e, r, c] = heap.pop()!;
    if (r === R - 1 && c === C - 1) return e;
    if (e > best[r][c]) continue;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
      const ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
      if (ne < best[nr][nc]) { best[nr][nc] = ne; heap.push([ne, nr, nc]); }
    }
  }
  return 0;
}

python

import heapq

def minimum_effort_path(heights):
    R, C = len(heights), len(heights[0])
    best = [[float("inf")] * C for _ in range(R)]
    best[0][0] = 0
    heap = [(0, 0, 0)]
    while heap:
        e, r, c = heapq.heappop(heap)
        if (r, c) == (R - 1, C - 1):
            return e
        if e > best[r][c]:
            continue
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C:
                ne = max(e, abs(heights[nr][nc] - heights[r][c]))
                if ne < best[nr][nc]:
                    best[nr][nc] = ne
                    heapq.heappush(heap, (ne, nr, nc))
    return 0

3Cheapest Flights Within K Stops (LeetCode 787)

🟠 Medium. flights[i] = (from, to, price). Return the cheapest price from src to dst with at most k stops (k + 1 flights), or −1.

text

0→1→3 costs 700 with k = 1 (0→1→2→3 = 400 needs 2 stops)

Approach. Bellman-Ford limited to k + 1 rounds. Each round relaxes every flight using a copy of the previous round's prices, so a round extends routes by exactly one flight.

Complexity. O(k · E) time, O(V) space.

typescript

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
  let price = new Array(n).fill(Infinity);
  price[src] = 0;
  for (let round = 0; round <= k; round++) {
    const next = [...price];
    for (const [u, v, w] of flights) if (price[u] + w < next[v]) next[v] = price[u] + w;
    price = next;
  }
  return price[dst] === Infinity ? -1 : price[dst];
}

python

def find_cheapest_price(n, flights, src, dst, k):
    INF = float("inf")
    price = [INF] * n
    price[src] = 0
    for _ in range(k + 1):
        nxt = price[:]                         # read from the previous round only
        for u, v, w in flights:
            if price[u] + w < nxt[v]:
                nxt[v] = price[u] + w
        price = nxt
    return price[dst] if price[dst] != INF else -1

4Shortest Path in Binary Matrix (LeetCode 1091)

🟠 Medium. Return the length (in cells) of the shortest clear path (0s) from top-left to bottom-right moving in 8 directions, or −1.

text

[[0,0,0],[1,1,0],[1,1,0]] → 4

Approach. Unweighted grid → BFS. Start at (0,0) if it's clear; each BFS level adds one cell to the path length.

Complexity. O(n²) time and space.

typescript

function shortestPathBinaryMatrix(grid: number[][]): number {
  const n = grid.length;
  if (grid[0][0] || grid[n - 1][n - 1]) return -1;
  const q: [number, number, number][] = [[0, 0, 1]];
  grid[0][0] = 1;
  for (let head = 0; head < q.length; head++) {
    const [r, c, d] = q[head];
    if (r === n - 1 && c === n - 1) return d;
    for (let dr = -1; dr <= 1; dr++) for (let dc = -1; dc <= 1; dc++) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && grid[nr][nc] === 0) { grid[nr][nc] = 1; q.push([nr, nc, d + 1]); }
    }
  }
  return -1;
}

python

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    q = deque([(0, 0, 1)])
    grid[0][0] = 1                                  # visited
    while q:
        r, c, d = q.popleft()
        if (r, c) == (n - 1, n - 1):
            return d
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    q.append((nr, nc, d + 1))
    return -1

5Swim in Rising Water (LeetCode 778)

🔴 Hard. At time t you can swim through cells with elevation ≤ t. Return the least time to go from top-left to bottom-right.

text

[[0,2],[1,3]] → 3

Approach. Minimax path: the cost of a path is its maximum elevation. Dijkstra with max (like Path With Minimum Effort), popping the lowest reachable elevation first; the max seen when reaching the target is the answer.

Complexity. O(n² log n).

typescript

class MinHeap<T> {
  private a: T[] = [];
  private less: (x: T, y: T) => boolean;
  constructor(less: (x: T, y: T) => boolean = (x: any, y: any) => x < y) { this.less = less; }
  get size(): number { return this.a.length; }
  peek(): T | undefined { return this.a[0]; }
  push(x: T): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {                                   // sift up
      const p = (i - 1) >> 1;
      if (!this.less(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]]; i = p;
    }
  }
  pop(): T | undefined {
    const a = this.a; if (!a.length) return undefined;
    const top = a[0], last = a.pop()!;
    if (a.length) {
      a[0] = last; let i = 0;
      while (true) {                                  // sift down
        const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]]; i = m;
      }
    }
    return top;
  }
}

function swimInWater(grid: number[][]): number {
  const n = grid.length;
  const seen = Array.from({ length: n }, () => new Array(n).fill(false));
  seen[0][0] = true;
  const heap = new MinHeap<[number, number, number]>((a, b) => a[0] < b[0]);
  heap.push([grid[0][0], 0, 0]);
  while (heap.size) {
    const [t, r, c] = heap.pop()!;
    if (r === n - 1 && c === n - 1) return t;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc]) {
        seen[nr][nc] = true;
        heap.push([Math.max(t, grid[nr][nc]), nr, nc]);
      }
    }
  }
  return -1;
}

python

import heapq

def swim_in_water(grid):
    n = len(grid)
    seen = {(0, 0)}
    heap = [(grid[0][0], 0, 0)]
    while heap:
        t, r, c = heapq.heappop(heap)
        if (r, c) == (n - 1, n - 1):
            return t
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
    return -1

6Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334)

🟠 Medium. Return the city with the fewest other cities reachable within distanceThreshold (ties: the largest index).

text

n = 4, threshold 4 → city 3

Approach. All-pairs shortest paths with Floyd–Warshall (n ≤ 100): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) for every intermediate k. Then count neighbours within the threshold for each city.

Complexity. O(n³) time, O(n²) space.

typescript

function findTheCity(n: number, edges: number[][], threshold: number): number {
  const d = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  for (const [u, v, w] of edges) d[u][v] = d[v][u] = Math.min(d[u][v], w);
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
  let bestCity = -1, bestCount = Infinity;
  for (let i = 0; i < n; i++) {
    const cnt = d[i].filter((x, j) => j !== i && x <= threshold).length;
    if (cnt <= bestCount) { bestCity = i; bestCount = cnt; }
  }
  return bestCity;
}

python

def find_the_city(n, edges, threshold):
    INF = float("inf")
    d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        d[u][v] = d[v][u] = min(d[u][v], w)
    for k in range(n):                        # allow k as an intermediate stop
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    best_city, best_count = -1, INF
    for i in range(n):
        cnt = sum(1 for j in range(n) if j != i and d[i][j] <= threshold)
        if cnt <= best_count:
            best_city, best_count = i, cnt
    return best_city

🧠 Key takeaways

Unweighted → BFS; 0/1 weights → deque; non-negative → Dijkstra; negative or ≤ k edges → Bellman-Ford.
Dijkstra: min-heap of (dist, node), skip stale entries, relax with d + w < dist[v].
Negative edges break Dijkstra's 'popped = final' guarantee.
Minimax paths (max edge) use Dijkstra with max instead of +; all pairs on small graphs → Floyd–Warshall.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_shortest_paths_exercise_1.py

TS PY

algo_shortest_paths_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Edges have weights 0 or 1. Fastest correct approach?

O(V + E).

2. Why does Dijkstra skip entries with d > dist[u]?

Lazy deletion.

3. Cheapest flight with at most k stops: why copy the previous round?

Limits edges per round.

4. Can Dijkstra handle negative edge weights?

Use Bellman-Ford.

Source: algo_shortest_paths_theory_1.md, algo_shortest_paths_theory_2.md · generated by tools/build_lessons.py