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