Shortest Path ·

Table of Contents

Introduction
#

Shortest path problems ask for the cheapest way to reach nodes in a graph. The main decision is which path model fits the constraints:

unweighted graph: BFS
non-negative weighted graph: Dijkstra
edge-count limit or negative-edge support: Bellman-Ford style DP
grid with non-sum path cost: Dijkstra can still work if path cost is monotonic

Dijkstra
#

Dijkstra works when extending a path never makes the path cost smaller. In normal weighted graphs, the path cost is a sum of non-negative edges.

from collections import defaultdict
from heapq import heappop, heappush
from typing import List

def dijkstra(n: int, edges: List[List[int]], src: int) -> List[float]:
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))

    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]

    while heap:
        cost, node = heappop(heap)
        if cost != dist[node]:
            continue
        for nei, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[nei]:
                dist[nei] = new_cost
                heappush(heap, (new_cost, nei))

    return dist

Minimax Dijkstra
#

Some graph problems do not sum edge weights. For example, a path’s effort might be the maximum edge effort used so far:

new_effort = max(current_effort, edge_effort)

Dijkstra still works because the path cost is monotonic: extending a path cannot reduce the effort already paid.

Bellman-Ford With K Stops
#

When a problem limits the number of edges, state must include the number of flights or layers used. For k stops, at most k + 1 flights are allowed.

from typing import List

def cheapest_with_k_stops(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    inf = float("inf")
    dist = [inf] * n
    dist[src] = 0

    for _ in range(k + 1):
        ndist = dist[:]
        for u, v, price in flights:
            if dist[u] != inf and dist[u] + price < ndist[v]:
                ndist[v] = dist[u] + price
        dist = ndist

    return -1 if dist[dst] == inf else dist[dst]

The copied array is important: one round should represent exactly one additional edge.

Put the Constraint in the State
#

When the limit is not the distance itself (say, at most k turns), put it in the state: (row, col, last direction, turns used).

pq = [(grid[0][0], 0, 0, 0, -1)]         # cost, turns, r, c, last direction
best_turns = {}                          # (r, c, d) -> fewest turns already processed
while pq:
    cost, t, r, c, d = heapq.heappop(pq)
    if (r, c) == target:
        return cost
    if best_turns.get((r, c, d), k + 1) <= t:
        continue                         # something cheaper with fewer turns was processed
    best_turns[(r, c, d)] = t
    for nd, (dr, dc) in enumerate(DIRS):
        nt = t + (d != -1 and nd != d)
        ...

For the same (r, c, d), whatever is popped first is cheaper; if it also used fewer turns, later states are dominated and can be skipped (LC 4046).

Common Mistakes
#

Using BFS on weighted graphs.
Saying the answer is the longest path instead of the maximum shortest arrival time.
Using city-only visited when remaining stops are part of the state.
Summing path costs when the real cost is a maximum along the path.
Forgetting stale heap entries in Dijkstra.
Operator precedence: turns + 1 if turned else 0 chooses between the whole expressions, so going straight reset the turn count to 0 (LC 4046).