Shortest Path Algorithms — 什麼時候用哪一個

Start: What's the shortest path problem?
│
├── Unweighted graph?
│   └── YES → BFS  O(V+E)
│
├── Single source or all pairs?
│   ├── ALL PAIRS
│   │   ├── V ≤ 400? → Floyd-Warshall  O(V³)
│   │   └── V > 400?  → Run Dijkstra from each vertex  O(V·(V+E) log V)
│   │
│   └── SINGLE SOURCE
│       ├── DAG? → Topo sort + relax  O(V+E)
│       ├── Negative weights?
│       │   ├── NO  → Dijkstra  O((V+E) log V)
│       │   └── YES → Bellman-Ford  O(V·E)
│       └── At most K edges?
│           └── Bellman-Ford with K iterations
│
└── Need negative cycle detection?
    ├── Single check → Bellman-Ford (V-th iteration)
    └── All pairs → Floyd-Warshall (check diagonal)

Graph:  A --1--> B --(-5)--> C
        A --3--> C

Dijkstra visits C via A→C (cost 3), marks C as done.
Misses A→B→C (cost 1+(-5) = -4).  ← WRONG ANSWER

Fix: Use Bellman-Ford.

Dijkstra alone doesn't work — K stop constraint means a longer
path might be cheaper. Need modified Bellman-Ford with K iterations,
or modified Dijkstra with state (node, stops_remaining).

// CORRECT: k (intermediate) must be outermost loop
for (int k = 0; k < V; k++)        // intermediate vertex
    for (int i = 0; i < V; i++)     // source
        for (int j = 0; j < V; j++) // destination
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

// WRONG: i or j as outermost loop gives incorrect results

LC 64 (Min Path Sum): only move right/down → DAG → use DP (simpler)
LC 1631 (Min Effort):  move 4 directions → cycles possible → use Dijkstra
LC 778 (Swim in Rising Water): 4 directions → Dijkstra or binary search + BFS

Rule: If movement is restricted to one direction (no cycles) → DP.
      If movement allows backtracking/cycles → Dijkstra.

# Time: O(V+E), Space: O(V)
from collections import deque

def bfs01(graph, src, n):
    dist = [float('inf')] * n
    dist[src] = 0
    dq = deque([src])

    while dq:
        u = dq.popleft()
        for v, w in graph[u]:  # w is 0 or 1
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)  # 0-weight → front
                else:
                    dq.append(v)      # 1-weight → back
    return dist

Minimize FEE, but total TIME must stay ≤ maxTime.

Cheapest-fee route may blow the time budget; the fastest route
may be expensive. Neither scalar alone dominates the other.

Popping by fee and marking node "done" is WRONG: the same node
reached later (higher fee) but FASTER can still lead to the answer.

Fix: make time part of the state.
     Keep bestTime[node]; only expand a state whose time strictly
     improves on every previously expanded time at that node.

Plain BFS/Dijkstra assumes: "first arrival at a node is final".
That breaks the moment the answer depends on HOW you arrived.

LC 847  : depends on which nodes are already visited  → state = (node, mask)
LC 1129 : depends on the color of the last edge used  → state = (node, lastColor)
LC 787  : depends on how many stops are left          → state = (node, stops)

Rule: seen/dist must be keyed by the FULL state, not by node.
      State count blows up the complexity by the size of the extra dimension.

// Dijkstra  (cheapest PATH from source)
if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;

// Prim / MST (cheapest TREE covering everything)   ← LC 1584
if (w < key[v]) key[v] = w;                  // no dist[u] term!

Dijkstra's greedy argument needs the path metric to be monotone
NON-IMPROVING as the path grows.

Sum of non-negative weights  : only grows  → min-heap Dijkstra  ✅
Product of probabilities ≤ 1 : only shrinks → max-heap Dijkstra ✅ (LC 1514)
Product of weights > 1       : grows unboundedly → Dijkstra ❌

// java
// time = O(n * 2^n), space = O(n * 2^n)
// IDEA: unweighted -> BFS, but the answer depends on WHICH nodes are already
//       visited, so the state is (node, visitedMask), not just node.
//       Start from every node at once (path may begin anywhere).
// LC 847 - Shortest Path Visiting All Nodes
public int shortestPathLength(int[][] graph) {
    int n = graph.length, full = (1 << n) - 1;
    boolean[][] seen = new boolean[n][1 << n];        // keyed by FULL state
    Deque<int[]> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {                     // multi-source start
        q.offerLast(new int[]{i, 1 << i});
        seen[i][1 << i] = true;
    }
    int steps = 0;
    while (!q.isEmpty()) {
        for (int sz = q.size(); sz > 0; sz--) {       // level by level
            int[] cur = q.pollFirst();
            if (cur[1] == full) return steps;
            for (int nxt : graph[cur[0]]) {
                int mask = cur[1] | (1 << nxt);
                if (!seen[nxt][mask]) {
                    seen[nxt][mask] = true;
                    q.offerLast(new int[]{nxt, mask});
                }
            }
        }
        steps++;
    }
    return 0;
}

# python
# time = O(n * 2^n), space = O(n * 2^n)
# IDEA: same as above - BFS whose visited set is keyed by (node, mask)
# LC 847 - Shortest Path Visiting All Nodes
from collections import deque

def shortestPathLength(graph):
    n = len(graph)
    full = (1 << n) - 1
    dq = deque((i, 1 << i, 0) for i in range(n))      # (node, mask, dist)
    seen = {(i, 1 << i) for i in range(n)}
    while dq:
        node, mask, d = dq.popleft()
        if mask == full:
            return d
        for nxt in graph[node]:
            nm = mask | (1 << nxt)
            if (nxt, nm) not in seen:
                seen.add((nxt, nm))
                dq.append((nxt, nm, d + 1))
    return 0

// java
// time = O(maxTime * E * log(maxTime * E)), space = O(maxTime * E)
// IDEA: two budgets (fee to minimize, time capped by maxTime). Pop by FEE, so
//       the first pop of node n-1 is the answer. A node may be expanded many
//       times - but only when it arrives with a STRICTLY better time.
// LC 1928 - Minimum Cost to Reach Destination in Time
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
    int n = passingFees.length;
    List<int[]>[] g = new List[n];
    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
    for (int[] e : edges) {
        g[e[0]].add(new int[]{e[1], e[2]});
        g[e[1]].add(new int[]{e[0], e[2]});
    }
    int[] bestTime = new int[n];
    Arrays.fill(bestTime, Integer.MAX_VALUE);
    // (cost, time, node) - ordered by cost
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{passingFees[0], 0, 0});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int cost = cur[0], time = cur[1], node = cur[2];
        if (node == n - 1) return cost;               // min cost, popped by cost
        if (time >= bestTime[node]) continue;         // pruning = the "state" check
        bestTime[node] = time;
        for (int[] nb : g[node]) {
            int nt = time + nb[1];
            if (nt <= maxTime) pq.offer(new int[]{cost + passingFees[nb[0]], nt, nb[0]});
        }
    }
    return -1;
}

# python
# time = O(maxTime * E * log(maxTime * E)), space = O(maxTime * E)
# IDEA: Dijkstra keyed by (node, time) - expand a node again only if it is
#       reached strictly faster than any earlier expansion of that node.
# LC 1928 - Minimum Cost to Reach Destination in Time
import heapq

def minCost(maxTime, edges, passingFees):
    n = len(passingFees)
    g = [[] for _ in range(n)]
    for u, v, t in edges:
        g[u].append((v, t))
        g[v].append((u, t))
    best_time = [float('inf')] * n
    pq = [(passingFees[0], 0, 0)]                     # (cost, time, node)
    while pq:
        cost, time, node = heapq.heappop(pq)
        if node == n - 1:
            return cost
        if time >= best_time[node]:
            continue
        best_time[node] = time
        for nxt, t in g[node]:
            if time + t <= maxTime:
                heapq.heappush(pq, (cost + passingFees[nxt], time + t, nxt))
    return -1

// java
// time = O(m*n), space = O(m*n)
// IDEA: changing a cell's arrow costs 1, following it costs 0 -> weights are
//       only {0,1}, so a deque replaces the heap: 0-edges to the FRONT,
//       1-edges to the BACK. The deque stays sorted by distance.
// LC 1368 - Minimum Cost to Make at Least One Valid Path in a Grid
public int minCost(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};   // grid value 1,2,3,4
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    Deque<int[]> dq = new ArrayDeque<>();
    dist[0][0] = 0;
    dq.offerFirst(new int[]{0, 0});
    while (!dq.isEmpty()) {
        int[] cur = dq.pollFirst();
        int r = cur[0], c = cur[1];
        for (int k = 0; k < 4; k++) {
            int nr = r + dir[k][0], nc = c + dir[k][1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int w = (grid[r][c] == k + 1) ? 0 : 1;      // arrow already points there?
            if (dist[r][c] + w < dist[nr][nc]) {
                dist[nr][nc] = dist[r][c] + w;
                if (w == 0) dq.offerFirst(new int[]{nr, nc});
                else        dq.offerLast(new int[]{nr, nc});
            }
        }
    }
    return dist[m - 1][n - 1];
}