Advanced Graphs

Beyond plain traversal

When edges have weights, BFS no longer gives the cheapest path. You need algorithms that expand by cost, plus the right one for the constraints (non-negative? negative? all-pairs? dense?). Picking correctly is the whole skill here.

Dijkstra — non-negative weights

Best-first search with a min-heap keyed by distance — O(E log V):

import heapq
def dijkstra(graph, src):                 # graph: node -> [(neighbor, weight)]
    dist = {src: 0}; pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")): continue   # stale entry (lazy decrease-key)
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd; heapq.heappush(pq, (nd, v))
    return dist

Powers “Network Delay Time,” “Path with Minimum Effort,” “Cheapest Flights” (with a hop limit, prefer Bellman–Ford). Requires non-negative weights — a negative edge breaks the greedy invariant.

Bellman–Ford — negative weights, cycle detection

Relax all edges V−1 times — O(V·E). Slower than Dijkstra but handles negative edges, and a V-th relaxation that still improves something reveals a negative cycle:

def bellman_ford(n, edges, src):          # edges: [(u, v, w)]
    dist = [float("inf")] * n; dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]: dist[v] = dist[u] + w
    # one more pass: any improvement → negative cycle
    return dist

Its bounded-relaxation form (k passes = “at most k edges”) solves Cheapest Flights Within K Stops.

Floyd–Warshall — all-pairs shortest paths

Dynamic programming over “paths using only the first k nodes as intermediates” — O(V³), simple, good for dense graphs or when you need every pair:

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Minimum spanning tree (connect all, min total weight)

• Prim’s — grow the tree, repeatedly adding the cheapest edge crossing the frontier (min-heap) — O(E log V); good for dense graphs.
• Kruskal’s — sort edges, add each that doesn’t form a cycle (union-find is the cycle check) — O(E log E); good for sparse/edge-list graphs.

Both solve “Min Cost to Connect All Points” / “Connecting Cities.”

Specialized algorithms (recognize them)

• 0-1 BFS — weights only 0/1: a deque (push 0-edges front, 1-edges back) gives O(V + E), beating Dijkstra.
• A* — Dijkstra plus a heuristic (lower-bound distance to target) to explore goal-ward; pathfinding on grids/maps.
• Topological sort + DP — shortest/longest path on a DAG in O(V + E) by relaxing in topo order (no heap needed).
• Strongly connected components — Tarjan’s / Kosaraju’s (O(V + E)) for directed cycles / condensation (“Critical Connections” uses the bridge-finding cousin).
• Max flow / min cut — Ford–Fulkerson / Dinic’s for matching and capacity problems; name it if the problem is bipartite matching or “max disjoint paths.”

Choosing the right one

Pitfalls

• Dijkstra with negative edges — wrong; use Bellman–Ford.
• Decrease-key — Python’s heap can’t update; push a new entry and skip stale pops (the d > dist[u] guard).
• Disconnected / unreachable — leave distances at infinity; handle them.
• Dense vs sparse — Floyd–Warshall (O(V³)) is fine dense, terrible sparse-large; match the algorithm to the graph.

State weight sign, source count, and density first — they pick the algorithm.