Shortest Path Algorithms

Seventeen quadrillion routes, one number per node

A signal leaves server S. Each cable delays it by a few milliseconds, and each cable carries traffic in one direction only. When does server T hear it?

               S
             ╱   ╲
          1 ╱     ╲ 4
           ╱       ╲
          ▼         ▼
          B ───2──► A
          │ ╲       │
        9 │   ╲ 5   │ 1
          │     ╲   │
          ▼       ↘ ▼
          T ◄──3─── C

The cables are S→B 1, S→A 4, B→A 2, B→C 5, B→T 9, A→C 1 and C→T 3.

Two obvious plans both fail.

Count hops. Breadth-first search finds the route with the fewest cables: S → B → T, two hops. It takes 1 + 9 = 10 ms. The route S → B → A → C → T uses four cables and takes 1 + 2 + 1 + 3 = 7 ms. BFS answers "fewest edges". This question asks for "least total weight", and that is a different question.

Try every route. This is correct, and hopeless. Connect 20 servers so that every server has a cable to every other one. That gives 380 one-way cables and 17,403,456,103,284,421 simple routes from S to T, about 1.7 × 10¹⁶.

The fix is to stop thinking about routes. For each node v, keep one number, dist[v]: the cheapest way to reach v found so far. Improve it with a single move, called relaxing the edge u → v with weight w:

if dist[u] + w < dist[v]:     # reaching v through u is cheaper
    dist[v] = dist[u] + w

That line is the whole lesson. Every algorithm below repeats it. They differ mainly in which edge they relax next, and sometimes in how a route is combined with its next edge. The safe order depends on what the weights are allowed to be. On the 20-server network, Dijkstra's order finishes after at most 381 heap pushes.

Throughout, V is the number of nodes and E the number of edges.

This lesson assumes you can model a problem as a graph and store it as an adjacency list (Graph Algorithms & Search), and that you know how BFS works and why it marks a node when it enters the queue (Graph Traversal). Dijkstra uses Python's heapq; Heaps & Priority Queues explains how the heap works inside. Unless a problem says otherwise, a graph here is a dict that maps every node to a list of (neighbor, weight) pairs.

Four words and one fact

• Tentative distance. dist[v] starts at float('inf') for every node except the source, which starts at 0. It is always the cost of some real route, so it is never below the true distance.
• Final. A node is final (or settled) once the algorithm can prove dist[v] will never drop again.
• Unreachable. A node whose dist is still infinite at the end. Problems usually want −1 or 0 for it, so read the contract.
• Negative cycle. A loop whose weights add up to less than zero. If the source can reach it and it can reach the target, going around once more always helps, so "shortest" has no answer.

Problems come in three shapes: single-source (one start, every target), single-pair (one start, one target, so you may stop early) and all-pairs (every start and every target).

The fact. Any part of a shortest route is itself a shortest route. Suppose the S → A part of the best S → T route had a cheaper alternative. Swap it in and the whole route gets cheaper, which contradicts "best". That is why one number per node is enough, and why one parent pointer per node is enough to rebuild the route afterwards.

Move 1: Every step costs the same, so BFS already works

Smell: "minimum number of moves / steps / transformations", and every move costs the same.

BFS takes nodes out of its queue in layers. Every node at distance d leaves the queue before any node at distance d + 1. So the first time you discover a node, you reach it from the nearest layer possible, and that distance is already final.

from collections import deque

def bfs_dist(graph, source):
    dist = {source: 0}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in dist:              # first discovery is the shortest
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist                            # a node missing from dist is unreachable

Why the first discovery is final. At every moment the queue holds some nodes at distance d followed by some at d + 1, never a third layer. You pop in that order, so any later discovery comes from a node at least as far away as the current one. That is O(V + E) time and O(V) extra space. Here dist doubles as the visited set, so a node is marked when it is discovered, as Graph Traversal teaches.

The word ladder

LeetCode 127: Word Ladder. You get beginWord, endWord and a wordList. One step changes exactly one letter, and every word after the first must be in the list. Return the number of words in the shortest sequence, or 0 if there is none. Constraints: words have length L ≤ 10, and the list holds up to 5,000 words.

Predict first: hit → cog with ["hot","dot","dog","lot","log","cog"]. How many words does the shortest sequence contain? What changes if "cog" is removed from the list?

Where is the graph? Each word is a node. Two words share an edge when they differ in exactly one position. Every edge costs one step, so this is BFS.

The slow version builds the edges by comparing every pair of words. With n = 5,000 and L = 10 that is 12,497,500 pairs, about 1.25 × 10⁸ character checks, before BFS even starts. Look at what it repeats. To find the neighbors of hot it scans all 4,999 other words, when all it needs are the words that fit *ot, h*t or ho*.

The fast version files each word under its L wildcard patterns once. Two words are neighbors exactly when they share a pattern.

from collections import defaultdict, deque

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    L = len(begin_word)
    buckets = defaultdict(list)              # "h*t" -> every listed word matching it
    for w in words:
        for i in range(L):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)

    seen = {begin_word}
    queue = deque([(begin_word, 1)])         # 1 = words in the sequence so far
    while queue:
        word, length = queue.popleft()
        if word == end_word:
            return length
        for i in range(L):
            for nxt in buckets[word[:i] + "*" + word[i + 1:]]:
                if nxt not in seen:
                    seen.add(nxt)            # mark on enqueue, as in plain BFS
                    queue.append((nxt, length + 1))
    return 0

Here is the search on the example, layer by layer:

cog leaves the queue with length 5.

Traps.

• Count what the problem counts. Word Ladder counts words, so start at 1. LeetCode 433: Minimum Genetic Mutation counts mutations, which are edges, so it starts at 0.
• The early end_word check is only a shortcut. The buckets hold only listed words, so the search could never reach an unlisted end_word anyway. The check just skips building the buckets.
• Mark on enqueue. If you mark on dequeue, a word can enter the queue once for every neighbor that is expanded before the word itself is dequeued. The answers stay correct, but the queue does extra work.

Cost. There are n·L patterns, and each one takes O(L) characters to build, both when filing the words and during the search. A bucket holds at most 26 words, one for each letter that can fill the star, so scanning it is cheap. That is O(n·L²) time, about 10⁶ character copies at the limits instead of about 10⁸ comparisons, and O(n·L²) space for the pattern keys.

Your turn: a binary maze

LeetCode 1091: Shortest Path in Binary Matrix. You get an n × n grid of 0s (open) and 1s (blocked). Move in 8 directions from the top-left cell to the bottom-right cell. The path length counts cells, not moves. Return −1 if there is no path. Predict the answers for [[0]], [[1]] and [[0,0,0],[1,1,0],[1,1,0]], then write it.

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1
    dist = [[0] * n for _ in range(n)]     # 0 = not reached yet
    dist[0][0] = 1                         # the length counts cells
    queue = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        if (r, c) == (n - 1, n - 1):
            return dist[r][c]
        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 and dist[nr][nc] == 0:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
    return -1

Move 2: Non-negative weights, so use Dijkstra

Smell: "minimum total time / cost / distance", and the constraints say every weight is ≥ 0.

The slow version, and what it repeats

One correct plan: relax every edge, and repeat until a full pass changes nothing. (That is Bellman–Ford, and Move 4 needs it.) It keeps relaxing the edges out of S and B on every pass, even though dist[S] and dist[B] can never change again. It learns nothing new about them, yet it pays for them every time.

Predict first: after relaxing S's two edges on the server graph, dist[B] = 1 and dist[A] = 4. Which of the two can you declare final right now, without looking at the rest of the graph?

The fast version: always expand the closest node

That rule is Dijkstra's algorithm. A min-heap hands you the smallest tentative distance in logarithmic time.

import heapq

graph = {
    'S': [('A', 4), ('B', 1)],
    'A': [('C', 1)],
    'B': [('A', 2), ('C', 5), ('T', 9)],
    'C': [('T', 3)],
    'T': [],                              # every node needs a key, even with no edges
}

def dijkstra(graph, source):
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    heap = [(0, source)]                  # (distance, node): distance first
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                   # stale: u improved after this entry was pushed
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:           # relax u -> v
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

print(dijkstra(graph, 'S'))   # {'S': 0, 'A': 3, 'B': 1, 'C': 4, 'T': 7}

heapq has no "decrease key" operation. When a node improves, you push a fresh entry and leave the old one where it is. An old entry is stale. When it reaches the top, its distance is larger than dist[u], and you skip it. This is called lazy deletion.

Here is the run, printed by the code. The heap is listed in sorted order so you can read it:

T was pushed with 10 and later with 7. The 7 comes out first, and the 10 is skipped when it finally surfaces.

🧠 Dijkstra is BFS with a sorted queue. BFS serves nodes by the number of steps taken; Dijkstra serves them by distance travelled. Set every weight to 1 and the heap pops nodes in exactly BFS's layer order.

Why a popped node is final

Say u pops with d == dist[u], the smallest value in the heap. Take any route from S to u. It starts among the final nodes, and at some edge x → y it first steps onto a node y that is not final. When x became final, its edges were relaxed, so dist[y] is at most the cost of the route up to y. The heap hands out the smallest value first, so d ≤ dist[y]. Everything after y has weight ≥ 0. So the route costs at least d. Every route to u costs at least d, and one costs exactly d, so d is final.

Only one step uses the non-negative weights: everything after y has weight ≥ 0. Keep an eye on it. Move 4 breaks exactly that step.

What it costs

• With weights ≥ 0, a node's dist cannot drop after it pops, so every node is expanded at most once and every edge is relaxed at most once. Each successful relaxation pushes one entry, so the heap receives at most E + 1 entries.
• A push or pop costs O(log E). Since E ≤ V², log E ≤ 2 log V, which is O(log V).
• Total: O((V + E) log V) time and O(V + E) extra space, for dist and up to E + 1 heap entries.

On a dense graph the heap stops paying off. The textbook array version scans all V nodes for the smallest unfinished dist, V times, which is O(V²) with no heap at all. On a complete graph with V = 1,000 (999,000 edges), that is about 10⁶ steps. The heap version may push up to about 10⁶ entries at roughly 20 comparisons each. Use the heap when E is close to V, as in most LeetCode graphs, and the array scan when E is close to V².

Traps

• Stop when the target is popped, not when it is pushed. For a single-pair question you may return as soon as the target pops, because it is final then. The first push of T carries 10, not 7.
• Mark a node final when it is popped, not when it is pushed. BFS marks on enqueue; Dijkstra cannot. Lock A when it is first pushed at 4 and S → B → A = 3 is never recorded. C then gets 6, and T gets 10. (On a grid where entering a cell costs the same from every side, marking on push happens to give right answers. Once the cost depends on the edge, as in Move 3's effort problem, it breaks.)
• Push (distance, node), in that order. Tuples compare element by element. With (node, distance) the heap pops nodes in name order. A version that finalizes on pop then reports T = 8 on the server graph. The lazy version above still ends with the right distances, but only because it re-expands nodes whose distance drops. The "each node once" bound is gone.
• Ties compare the node. When two distances are equal, Python compares the second item. Integers, strings and tuples such as (row, col) compare fine. Objects without < raise TypeError, so push (d, counter, node) with a running counter.
• The stale check saves time, not correctness. With weights ≥ 0, a stale pop relaxes from a larger d and cannot beat values already set. Skipping it saves re-scanning that node's edge list, which matters when a node with many edges has many stale copies.
• Start at infinity, not 0. With every dist at 0, d + w < dist[v] is never true, and every node reports 0.
• Undirected input means two edges. Add (v, w) to graph[u] and (u, w) to graph[v].
• No cleanup needed for parallel edges (the cheaper one wins the relaxation) or for self-loops with w ≥ 0 (they never improve anything).

Your turn: Network Delay Time

LeetCode 743: Network Delay Time. Nodes are labelled 1 to n. times[i] = [u, v, w] is a directed edge taking w time. A signal starts at node k. Return the time until every node has received it, or −1 if some node never does. Constraints: n ≤ 100, up to 6,000 edges, 0 ≤ w ≤ 100.

Example: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 gives 2. Write it, then predict times = [[1,2,1]], n = 2, k = 2.

import heapq
from collections import defaultdict

def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))            # directed
    dist = [float('inf')] * (n + 1)        # nodes are 1..n; slot 0 unused
    dist[k] = 0
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    slowest = max(dist[1:])
    return slowest if slowest < float('inf') else -1

Getting the route, not just its length

Record where each improvement came from. The last improvement to a node is the one that matches its final distance.

def dijkstra_path(graph, source, target):
    dist = {node: float('inf') for node in graph}
    dist[source] = 0
    parent = {source: None}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        if u == target:                    # popped, so final: safe to stop
            break
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u              # only when the distance improves
                heapq.heappush(heap, (dist[v], v))
    if dist[target] == float('inf'):
        return float('inf'), []
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    return dist[target], path[::-1]

print(dijkstra_path(graph, 'S', 'T'))   # (7, ['S', 'B', 'A', 'C', 'T'])

One pointer per node is O(V) memory. Storing a whole copied route for every node can cost O(V) per node, which is O(V²) in total.

Move 3: Change what "cost" means

Smell: a route's score is not a plain sum. "The largest climb along the path." "The probability that every link survives." "The water level you must wait for."

The proof in Move 2 used two facts about sums of non-negative weights:

1. Extending a route never makes it better.
2. Ahead stays ahead. If route P to u beats route Q to u, then P plus the edge u → v is at least as good as Q plus the same edge. That is why one best value per node is enough.

Any score with both properties works with the same code. Only the line that combines a route with its next edge changes, and sometimes the direction of the heap.

A negative weight breaks fact 1 for sums. A factor above 1 breaks it for products, because the product can then grow as the route gets longer.

The gentlest hike

LeetCode 1631: Path With Minimum Effort. Walk from the top-left to the bottom-right of a heights grid, moving in 4 directions. A route's effort is its largest absolute height difference between neighboring cells. Minimize it. The grid is at most 100 × 100.

Predict first: heights = [[1,2,2],[3,8,2],[5,3,5]]. Plain Dijkstra on the total climb picks one route. Is that route's effort the answer?

import heapq

def minimum_effort_path(heights):
    rows, cols = len(heights), len(heights[0])
    effort = [[float('inf')] * cols for _ in range(rows)]
    effort[0][0] = 0
    heap = [(0, 0, 0)]                     # (worst step so far, row, col)
    while heap:
        e, r, c = heapq.heappop(heap)
        if e > effort[r][c]:
            continue
        if (r, c) == (rows - 1, cols - 1):
            return e
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                ne = max(e, abs(heights[nr][nc] - heights[r][c]))   # max, not +
                if ne < effort[nr][nc]:
                    effort[nr][nc] = ne
                    heapq.heappush(heap, (ne, nr, nc))
    return effort[rows - 1][cols - 1]

With V = rows·cols cells and about 4V edges, this is O(V log V) time and O(V) space. There is another way in: binary search on the answer, and for each guess run a BFS that only takes steps no larger than the guess. Keep both in mind. The binary-search version works whenever "can I finish with limit x?" gets easier as x grows.

Your turn: the safest route

LeetCode 1514: Path with Maximum Probability. The graph is undirected, and edge i survives with probability succProb[i]. Return the highest probability of getting from start to end, or 0 if you cannot get there. Example: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 gives 0.25. Constraints: n ≤ 10⁴, up to 2 × 10⁴ edges.

import heapq
from collections import defaultdict

def max_probability(n, edges, succ_prob, start, end):
    graph = defaultdict(list)
    for (a, b), p in zip(edges, succ_prob):
        graph[a].append((b, p))            # undirected: both directions
        graph[b].append((a, p))
    best = [0.0] * n
    best[start] = 1.0
    heap = [(-1.0, start)]                 # heapq is a min-heap, so negate
    while heap:
        neg_p, u = heapq.heappop(heap)
        p = -neg_p
        if p < best[u]:                    # stale
            continue
        if u == end:
            return p
        for v, q in graph[u]:
            if p * q > best[v]:
                best[v] = p * q
                heapq.heappush(heap, (-best[v], v))
    return 0.0

Move 4: Plot twist, the weights go negative

Smell: weights can be negative. Refunds, "gain energy on this tile", height drops, −log of an exchange rate.

Predict first: edges A→B 1, A→C 5, C→B −10, B→D 1. Run a Dijkstra that marks each node final when it pops. What does it report for D, and what is the truth?

        1         1
   A ──────► B ──────► D
   │         ▲
 5 │         │ −10
   ▼         │
   C ────────┘

The broken step is the one flagged in Move 2: everything after y has weight ≥ 0. The route A → C → B steps onto C at 5 and then drops by 10.

What about the lazy version? On this graph it gets −4. When B drops to −5, it pushes B again and re-expands it. The lazy version keeps relaxing until nothing improves, so with no negative cycle it ends with the right distances. But it is no longer Dijkstra:

• The early exit is wrong. Asked only for D, it pops D at 2, before C, and returns 2.
• "Each node once" is gone. There are graphs with no cycles at all where V nodes cause 2^(V−1) expansions. With 18 nodes and 153 edges that is 131,072 expansions, where Bellman–Ford needs at most 17 rounds of 153 relaxations each (2,601).

Don't shift the weights. Adding a constant c to every edge adds c times the number of edges to each route, so it punishes routes with many edges. Take S→T 1, S→A 2, A→T −2. The best route is S → A → T with cost 0. Add 2 everywhere and S→T becomes 3 while S → A → T becomes 4 + 0 = 4, so the shifted graph picks the route that really costs 1. (Johnson's reweighting, at the end of this lesson, shifts each node instead, and that version is safe.)

Bellman–Ford: relax everything, V − 1 times

If there is no negative cycle, some shortest route never repeats a node, so it uses at most V − 1 edges. Relax every edge once and you have found the best route of at most one edge to every node. Relax them all again and you have every best route of at most two edges. Keep going.

def bellman_ford(n, edges, source):
    dist = [float('inf')] * n
    dist[source] = 0
    for _ in range(n - 1):                 # at most n - 1 rounds
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:      # inf + w stays inf, so no guard needed
                dist[v] = dist[u] + w
                changed = True
        if not changed:                    # a quiet round: every later round is quiet too
            break
    for u, v, w in edges:                  # one more pass: does anything still improve?
        if dist[u] + w < dist[v]:
            return None                    # a negative cycle is reachable from source
    return dist

Invariant: after round i, dist[v] is at most the cost of the best route to v that uses at most i edges. It is also always the cost of some real route, so it never drops below the truth.

Here is a trace with the edges listed in an unlucky order: [(2,3,2), (1,3,6), (1,2,-3), (0,2,5), (0,1,4)], four nodes, source 0.

The best route to 3 is 0 → 1 → 2 → 3, with cost 4 − 3 + 2 = 3. It has three edges, so the invariant says it is found by round 3, and it is. List the same edges from 0 outward and round 1 finds everything. Round 2 then changes nothing, and the loop stops early.

Negative cycles. After V − 1 rounds, with no reachable negative cycle, every dist is already exact and nothing can improve. With one, something always can. Add up dist[v] − dist[u] around the cycle and you get 0, while the weights add up to less than 0. So at least one cycle edge must satisfy dist[u] + w < dist[v].

Arbitrage. Converting USD→EUR at 0.9, EUR→GBP at 0.9 and GBP→USD at 1.3 turns 1 dollar into 0.9 × 0.9 × 1.3 = 1.053 dollars. Use the weight w = −ln(rate). A product above 1 is then a sum below 0: 0.105 + 0.105 − 0.262 = −0.052, which is a negative cycle.

import math

rates = [("USD", "EUR", 0.9), ("EUR", "GBP", 0.9), ("GBP", "USD", 1.3)]
index = {"USD": 0, "EUR": 1, "GBP": 2}
edges = [(index[a], index[b], -math.log(r)) for a, b, r in rates]
print(bellman_ford(3, edges, 0))   # None: a profitable loop exists

This only finds cycles that the source can reach. To check the whole graph, start every dist at 0 instead. That acts like a virtual source with a 0-weight edge to every node.

Traps.

• Too few rounds invents a cycle. Run only 2 rounds on the unlucky graph and the check sees 2 → 3 improve from 7 to 3, so it returns None although no cycle exists. An extra round costs time but never changes the answer.
• The infinity guard depends on your sentinel. In Python, inf + w stays inf, so the code needs no guard. With a finite sentinel such as 10**9, an unreachable node with a −5 edge produces 999,999,995, which looks like a real distance. In Java or C++, INT_MAX + w can overflow. There you need if dist[u] == INF: continue.
• A negative cycle you cannot reach is not reported, and it affects nothing, because those nodes stay at infinity.

Cost: O(V · E) time and O(V) extra space. A queue-based variant called SPFA re-relaxes only the edges out of nodes that just improved. It is often faster in practice, and its worst case is the same O(V · E).

Move 5: A budget on edges

Smell: "at most k stops / edges / moves", and the edges have weights.

LeetCode 787: Cheapest Flights Within K Stops. flights[i] = [from, to, price]. Return the cheapest price from src to dst using at most k stops, or −1. Constraints: n ≤ 100 cities, prices from 1 to 10⁴, 0 ≤ k < n. k stops means at most k + 1 flights. (When a problem limits edges to k instead, run k rounds.)

Predict first: flights [[0,1,100],[1,2,100],[0,2,500],[2,3,100]], from 0 to 3, k = 1. Without the limit the cheapest route is 0 → 1 → 2 → 3 for 300. What is the answer?

Why Dijkstra by price fails. Dijkstra keeps one best price per city. It settles city 2 at 200 (two flights) and drops the 500 route (one flight) because it costs more. But only the 500 route has a flight left in the budget for 2 → 3. A version that refuses to extend a route past k + 1 flights returns −1 here. Fact 2 of Move 3 has failed: a cheaper route to city 2 is not better if it used more of the budget.

The fix is already in Move 4. Bellman–Ford's round i finds every best route with at most i edges. Run exactly k + 1 rounds, and make each round read only the previous round's prices.

def find_cheapest_price(n, flights, src, dst, k):
    prices = [float('inf')] * n
    prices[src] = 0
    for _ in range(k + 1):                 # k stops = at most k + 1 flights
        nxt = prices[:]                    # read the old round, write the new one
        for u, v, p in flights:
            if prices[u] + p < nxt[v]:
                nxt[v] = prices[u] + p
        prices = nxt
    return prices[dst] if prices[dst] < float('inf') else -1

The answer is 600.

The trap: updating in place. Drop the copy and write straight into prices, and round 1 can use the price of city 1 it has just set, chaining 0 → 1 → 2 inside a single round. On the predict graph that returns 300. On LeetCode's own three-city example ([[0,1,100],[1,2,100],[0,2,500]], from 0 to 2 with k = 0) it returns 200 instead of 500. nxt = prices without [:] is the same bug in disguise, because both names point at one list.

Why the copy fixes it: every candidate in round i is built from a round-(i − 1) price, so it adds exactly one flight to a route of at most i − 1 flights.

A search over states (city, flights used) with Dijkstra or BFS also works. Bellman–Ford rounds are the shortest correct code. Cost: O((k + 1) · (n + E)) time for k + 1 rounds, each copying n prices and scanning E flights, and O(n) extra space.

Your turn: flights [[0,1,1],[0,2,5],[1,2,1],[2,3,1]], from 0 to 3. Give the answers for k = 0, 1 and 2.

Move 6: Weights of 0 and 1, so use a deque

Smell: every move is either free or costs exactly one. "Follow the arrow for free, change it for 1." "Walk through empty cells for free, remove an obstacle for 1."

LeetCode 1368: Minimum Cost to Make at Least One Valid Path in a Grid. Each cell holds a sign: 1 points right, 2 left, 3 down, 4 up. You start at the top-left. Following the sign is free, and changing a cell's sign costs 1. Return the minimum cost of a path to the bottom-right. The grid is at most 100 × 100. Example: [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]] gives 3.

Predict first: why can't BFS's plain FIFO queue handle a free move?

That is 0-1 BFS: a deque, where a 0-edge goes to the front with appendleft and a 1-edge goes to the back with append. Invariant: from front to back, the distances in the deque never decrease, and they span at most two values, d and d + 1. So the front always holds the smallest distance, as Dijkstra's heap would, but you get it in O(1).

from collections import deque

def min_cost(grid):
    m, n = len(grid), len(grid[0])
    moves = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
    dist = [[float('inf')] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0, 0)])                # (cost, row, col)
    while dq:
        d, r, c = dq.popleft()
        if d > dist[r][c]:
            continue                       # stale: this cell improved later
        if (r, c) == (m - 1, n - 1):
            return d
        for sign, (dr, dc) in moves.items():
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                w = 0 if grid[r][c] == sign else 1
                if d + w < dist[nr][nc]:
                    dist[nr][nc] = d + w
                    if w == 0:
                        dq.appendleft((d, nr, nc))
                    else:
                        dq.append((d + 1, nr, nc))
    return dist[m - 1][n - 1]

Traps.

• A cell can enter the deque twice: first at d + 1 through a 1-edge, then at d through a 0-edge. Keep dist and skip stale entries, just as in Dijkstra.
• Return on pop. The front is the minimum only when you pop it.
• Appending the free moves to the back breaks it. With that one change, [[1,1,3],[3,2,2],[1,1,4]] returns 1 instead of 0. A FIFO queue serves the cost-1 entries queued earlier before the cost-0 entries queued after them, so the goal is first reached along a cost-1 route.

Cost: each cell enters the deque at most twice, so the time is O(m·n) with 4 edges per cell, and the space is O(m·n). Dijkstra on the same grid would be O(m·n·log(m·n)).

Your turn: which weight sets can this deque trick handle? {0, 1}, {0, 7}, {1, 2}, {0, 1, 2}.

Move 7: Every pair at once

Smell: many questions about arbitrary pairs of nodes, and V is small, a few hundred at most.

Floyd–Warshall grows the set of nodes a route may pass through. Let dist[i][j] be the best route from i to j whose middle nodes all come from {0, …, k − 1}. Now allow node k as well. The best route either avoids k, and keeps its old value, or goes i → k → j and costs dist[i][k] + dist[k][j].

def floyd_warshall(n, edges):
    INF = float('inf')
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)    # keep the cheapest parallel edge
    for k in range(n):                     # k, the allowed middle node, is OUTERMOST
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Predict first: does the loop order matter? Could k be the innermost loop?

Updating the matrix in place is safe. During phase k, row k and column k do not change, because dist[k][k] is 0 as long as there is no negative cycle. Negative edges are fine. A negative cycle through i shows up as dist[i][i] < 0 at the end.

Worked example. LeetCode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance. The edges are undirected, and n ≤ 100. For each city, count the other cities within distanceThreshold. Return the city with the fewest, and on a tie the one with the largest index.

def find_the_city(n, edges, distance_threshold):
    both_ways = edges + [[v, u, w] for u, v, w in edges]   # undirected
    dist = floyd_warshall(n, both_ways)
    best_city, best_count = -1, n + 1
    for i in range(n):
        count = sum(1 for j in range(n) if j != i and dist[i][j] <= distance_threshold)
        if count <= best_count:            # <= keeps the larger index on ties
            best_city, best_count = i, count
    return best_city

print(find_the_city(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4))   # 3

Cities 0 and 3 can each reach two others within 4, and the tie goes to 3.

Cost: O(V³) time and O(V²) space. V = 100 is 10⁶ inner steps. V = 400 is 6.4 × 10⁷, which takes a couple of seconds in pure Python. The alternative is Dijkstra from every node, O(V · (V + E) log V). That wins on sparse graphs. Floyd–Warshall wins on dense ones, handles negative edges, and is five lines long.

Beyond the interview: three names you will hear

• A* orders the heap by dist[v] + h(v), where h guesses the remaining distance to the target. If h never overestimates (it is admissible) and never drops by more than an edge's weight along that edge, so that h(u) ≤ w(u, v) + h(v) (it is consistent), every node still settles once with its true distance. With h = 0 it is exactly Dijkstra. On a grid with unit moves in 4 directions, Manhattan distance is a consistent h.
• Bidirectional search runs one search forward from the source and one backward from the target over reversed edges. Stopping at the first node settled by both is wrong. With edges 1→2 (7), 2→0 (3) and 1→0 (8), searching from 1 to 0, the searches meet at node 2 with 7 + 3 = 10, but the direct edge costs 8. The correct rule keeps μ, the best df[v] + db[v] seen at any node reached from both sides, and stops only when the two heaps' smallest keys add up to at least μ. With unit weights, branching factor b and answer depth d, two half-depth searches touch about 2·b^(d/2) nodes instead of b^d. On grid-like graphs the saving is about half the area, because 2·(r/2)² = r²/2.
• Johnson's algorithm gives all pairs on sparse graphs with negative edges. One Bellman–Ford run computes a potential h(v) for every node. Then w'(u, v) = w(u, v) + h(u) − h(v) is never negative, and V Dijkstra runs finish the job. Unlike adding a constant per edge, this shifts every s → t route by the same h(s) − h(t), so the best route stays the best.

Road maps at continental scale add heavy preprocessing on top of these ideas, such as contraction hierarchies, so a query touches only a tiny part of the graph. That is beyond interview scope.

Final round: no label on the problem

Real problems don't name the algorithm. For each one, decide what a node is, what an edge costs, and which move fits, before you open the answer.

Challenge 1: the frog changes lanes

LeetCode 1824: Minimum Sideway Jumps. A road has 3 lanes and points 0 to n (n ≤ 5 × 10⁵). obstacles[i] is the lane (1, 2 or 3) blocked at point i, or 0 for none. A frog starts at point 0 in lane 2. It may step forward along its lane if the next point in that lane is free, or jump sideways to any other free lane at the same point. Return the fewest sideways jumps needed to reach point n in any lane. Example: obstacles = [0,1,2,3,0] gives 2.

from collections import deque

def min_side_jumps(obstacles):
    n = len(obstacles) - 1
    dist = [[float('inf')] * 3 for _ in range(n + 1)]   # dist[point][lane], lanes 0, 1, 2
    dist[0][1] = 0                                     # start in the middle lane
    dq = deque([(0, 0, 1)])                            # (jumps, point, lane)
    while dq:
        d, p, lane = dq.popleft()
        if d > dist[p][lane]:
            continue
        if p == n:
            return d
        if obstacles[p + 1] != lane + 1 and d < dist[p + 1][lane]:
            dist[p + 1][lane] = d                      # step forward: free
            dq.appendleft((d, p + 1, lane))
        for other in range(3):                         # side jump: costs 1
            if other != lane and obstacles[p] != other + 1 and d + 1 < dist[p][other]:
                dist[p][other] = d + 1
                dq.append((d + 1, p, other))

print(min_side_jumps([0, 1, 2, 3, 0]))   # 2

Challenge 2: stay far from the thieves

LeetCode 2812: Find the Safest Path in a Grid. An n × n grid (n ≤ 400) has thieves (1) and empty cells (0). A cell's safeness is its Manhattan distance to the nearest thief. A route from the top-left to the bottom-right, moving in 4 directions, is as safe as its least safe cell. Return the largest possible safeness of a route. Example: [[0,0,1],[0,0,0],[0,0,0]] gives 2.

import heapq
from collections import deque

def maximum_safeness_factor(grid):
    n = len(grid)
    moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
    safe = [[-1] * n for _ in range(n)]                # distance to the nearest thief
    queue = deque()
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                safe[r][c] = 0
                queue.append((r, c))
    while queue:                                       # BFS from every thief at once
        r, c = queue.popleft()
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and safe[nr][nc] == -1:
                safe[nr][nc] = safe[r][c] + 1
                queue.append((nr, nc))
    best = [[-1] * n for _ in range(n)]                # best weakest-cell value so far
    best[0][0] = safe[0][0]
    heap = [(-safe[0][0], 0, 0)]                       # max-heap: push the negated value
    while heap:
        neg, r, c = heapq.heappop(heap)
        s = -neg
        if s < best[r][c]:
            continue
        if (r, c) == (n - 1, n - 1):
            return s
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n:
                ns = min(s, safe[nr][nc])              # a route is as safe as its worst cell
                if ns > best[nr][nc]:
                    best[nr][nc] = ns
                    heapq.heappush(heap, (-ns, nr, nc))

print(maximum_safeness_factor([[0, 0, 1], [0, 0, 0], [0, 0, 0]]))   # 2

Challenge 3: only walk downhill

LeetCode 1786: Number of Restricted Paths From First to Last Node. The graph is undirected and weighted, with nodes 1 to n (n ≤ 2 × 10⁴, up to 4 × 10⁴ edges). Let d(x) be the shortest distance from x to node n. Count the paths from 1 to n along which d strictly decreases at every step, modulo 10⁹ + 7.

import heapq
from collections import defaultdict

def count_restricted_paths(n, edges):
    MOD = 10**9 + 7
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    dist = [float('inf')] * (n + 1)
    dist[n] = 0
    heap = [(0, n)]
    while heap:                            # Dijkstra from the LAST node
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    ways = [0] * (n + 1)
    ways[n] = 1
    for u in sorted(range(1, n + 1), key=lambda x: dist[x]):   # nearest to n first
        for v, _ in graph[u]:
            if dist[v] < dist[u]:
                ways[u] = (ways[u] + ways[v]) % MOD
    return ways[1]

print(count_restricted_paths(5, [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]))   # 3

Challenge 4: which course needs which

LeetCode 1462: Course Schedule IV. There are n ≤ 100 courses, and a prerequisite pair [a, b] means a must come before b. Prerequisites chain: if a comes before b and b before c, then a comes before c. Up to 10⁴ queries each ask "is u a prerequisite of v?"

Cheat sheet

Before moving on, pick one problem from this lesson and explain it aloud from a blank editor. Say what a node is, what an edge costs, and which ordering of relaxations is safe for those weights. Say what dist means at the moment a node is popped, which single step of the correctness argument the weights must support, and which input would break your choice: a negative edge, a stop limit, a max instead of a sum. If you can do that, the rest is details.

Next: Trees & Advanced Structures for tree-shaped graphs and range-query structures, Heaps & Priority Queues for what heapq does inside Dijkstra, and Dynamic Programming Mastery, where Bellman–Ford's "best with at most i edges" and Floyd–Warshall's "best through the first k nodes" become a general method.