Graph algorithms

1 · Why graph algorithms are the senior-interview hot topic

Every system that matters models something as a graph. Roads are a graph (intersections are nodes, road segments are weighted edges). Networks are a graph (routers are nodes, links are edges with latency). Dependency trees are a graph. Friendships are a graph. The moment you read a problem and notice "this is a network with costs", you are no longer in BFS / DFS territory — you are reaching for one of six named algorithms.

The recognition signal that fires for senior-loop questions is specific: "shortest path with weighted edges" almost always means Dijkstra (or Bellman-Ford if any edge weight can go negative). "Connect every vertex cheaply" means MST (Prim or Kruskal). "Are these directed components mutually reachable" means Tarjan or Kosaraju for SCC. The hard part isn't writing the algorithm — it's the recognition.

Real production examples

• Google Maps / Waze routing. Bidirectional Dijkstra on the road network, augmented with contraction hierarchies for continental-scale queries (sub-millisecond response on a million-node graph). The textbook algorithm with industrial-strength preprocessing.
• TCP/IP routing protocols. OSPF (Open Shortest Path First) runs Dijkstra over a link-state database. RIP uses Bellman-Ford in distributed form (each router relaxes edges in its own table). Both are direct applications.
• Package managers (npm, pip, apt). Topological sort on the dependency graph, with cycle detection. If a cycle exists, no install order is valid — emit an error. If none exists, install in reverse topological order.
• Flight pricing engines. Modified Dijkstra over an airline network where each edge weight is the fare, with side constraints (max layovers, fare class compatibility). The "Cheapest Flights Within K Stops" problem is literally what every booking site solves.
• Social-graph friend recommendations. BFS with depth limit (find friends-of-friends within 2 hops), then rank by mutual-friend count. Facebook's "People You May Know" is exactly this, plus a learned re-ranker.
• Build systems (Bazel, Make, Buck). Topological sort of build targets. Parallel scheduling falls out of the DAG structure: independent subtrees build concurrently.

2 · How to recognise it

The trigger is a weighted graph — the moment edge weights matter, BFS is no longer enough. From there the right algorithm depends on what's being asked. Six recognisable shapes cover almost every interview question.

Shape A — shortest path between two nodes

• Unweighted (or all weights equal) → BFS. O(V + E). The depth at which a node is first visited is its shortest distance from the source.
• Non-negative weights → Dijkstra. O((V + E) log V) with a binary heap. The default when edges have positive costs.
• Possibly negative weights → Bellman-Ford. O(V · E). Slower than Dijkstra but tolerates negative edges and detects negative cycles in an extra iteration.

Shape B — all-pairs shortest paths

• Floyd-Warshall. O(V³) DP. Three nested loops over intermediate vertices. Worth it when V is small (V ≤ 400) and you need every pair.
• Johnson's algorithm. O(V · E log V) — sparse all-pairs by re-weighting edges to be non-negative, then running Dijkstra from every source. Beats Floyd-Warshall when E ≪ V².
• N independent Dijkstras. O(V · (V + E) log V). The pragmatic option when the graph has no negative edges.

Shape C — minimum spanning tree

• Kruskal. O(E log E). Sort edges by weight; for each, union endpoints with union-find if they're in different components. Pairs naturally with DSU.
• Prim. O((V + E) log V) with a heap, O(V²) with a plain array (better for dense graphs). Grows the tree from a seed vertex outward.
• Borůvka. O(E log V). Parallelism-friendly: each round, every component finds its cheapest outgoing edge and merges. Used in distributed MST.

Shape D — maximum flow / matching

• Ford-Fulkerson. The generic framework. Find augmenting paths until none exists; total flow = max flow.
• Edmonds-Karp. Ford-Fulkerson with BFS for the augmenting path. O(V · E²). Polynomial bound.
• Dinic's algorithm. O(V² · E) in general, O(E · √V) on bipartite matching. The default for serious flow problems.
• Hopcroft-Karp. O(E · √V) for bipartite matching specifically.

Shape E — strongly connected components

• Tarjan. O(V + E). One DFS pass with discovery times and low-link values. The classic.
• Kosaraju. O(V + E). Two DFS passes — one on the original graph in post-order, one on the transpose. Easier to explain on a whiteboard.

Shape F — shortest path with state

• The signal: "shortest path subject to a side constraint" — at most K stops, fuel limit, time-of-day windows, must-visit set.
• The reframing: the graph becomes a product graph where each node is (original_node, state) and you run standard Dijkstra on the product. LC 787 cheapest flights with K stops is the canonical example — state is "stops used so far".
• Cost blow-up: if state has S possible values, the product graph has V · S nodes. Watch the memory and time budget.

3 · Sister algorithms

Beyond the canonical six, a cluster of related algorithms shows up when the standard ones don't quite fit. Knowing the names — and roughly when each one wins — is the depth check senior interviewers look for.

• Bellman-Ford. O(V · E). Single-source shortest path that tolerates negative weights. V − 1 rounds of edge relaxation; a Vth round that still relaxes any edge proves a negative cycle. The arbitrage-detection algorithm at every quant shop.
• SPFA (Shortest Path Faster Algorithm). Bellman-Ford with a queue — only re-process nodes whose distance just decreased. Average-case dramatically faster than Bellman-Ford on sparse graphs, worst-case still O(V · E). Banned from some Chinese OJs because the worst case is constructible.
• Floyd-Warshall. O(V³) all-pairs DP. The three nested loops for k for i for j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) are deceptively short. Detects negative cycles (any diagonal entry < 0 after the algorithm). Constant factor is tiny — beats N Dijkstras for V ≤ ~300.
• A* (A-star). Dijkstra plus a heuristic h(node) that under-estimates remaining distance to the goal. Optimal when h is admissible (never over-estimates) and consistent. On grid maps with Manhattan distance, A* expands an order of magnitude fewer nodes than vanilla Dijkstra. Every modern pathfinder uses some variant.
• Bidirectional Dijkstra. Run two Dijkstras simultaneously — one from source, one from target. Stop when they meet. The frontier of each search is roughly √(target's full frontier), so total work is √N of vanilla. Combined with contraction hierarchies, this is what powers Google Maps.
• Johnson's algorithm. All-pairs shortest paths in O(V · E log V) for sparse graphs. Add a virtual node connected to every vertex with weight 0, run Bellman-Ford from it to get re-weighting potentials, then run Dijkstra from each source on the re-weighted graph. Faster than Floyd-Warshall when E is much less than V².
• 0/1 BFS (deque BFS). Special case of Dijkstra when edge weights are only 0 or 1. Use a deque instead of a heap: push-front for weight-0 edges, push-back for weight-1. O(V + E). LC 1368 Minimum Cost to Make at Least One Valid Path in a Grid is the classic.
• Yen's K-shortest paths. Find the K shortest loop-less paths between two nodes. O(K · V · (E + V log V)). Used in transit routing (give me three alternative subway routes), failover planning, redundancy analysis.

4 · Canonical example — Network Delay Time (LC 743)

Problem. A network of n nodes labelled 1..n. times[i] = (u, v, w) means a signal from u reaches v after w units of time. Send a signal from node k; return the time it takes for every node to receive it, or -1 if some node never does.

Input:  times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: <a class="il" href="/simulators/dijkstra-pathfinding">Dijkstra</a> from k=2. Distances: {2:0, 1:1, 3:1, 4:2}.
             Max distance = 2; every node reachable.

Run Dijkstra from source k. The answer is the maximum value in the distance map (the time the slowest node receives the signal), or -1 if any node is unreached. Cost is O((V + E) log V).

5 · Reference implementation

import heapq
from collections import defaultdict

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    dist = {}                          # final shortest distances
    heap = [(0, k)]                    # (distance_so_far, node)

    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                   # STALE: already finalised a shorter path
        dist[u] = d
        for v, w in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))   # relaxation step

    if len(dist) < n:
        return -1                      # some node unreachable
    return max(dist.values())

6 · Variations

Six named algorithms, six different shapes. The one you reach for is determined by the question, not by preference.

6a · Dijkstra on a 6-node graph, step by step

Dijkstra's algorithm keeps a min-heap of (distance, node) tuples. Each iteration: pop the smallest, mark finalised, relax all its outgoing edges. Watching it run on a small graph makes the invariant click — every finalised distance is the actual shortest from source.

6b · Picking the right algorithm

Half of getting a graph problem right is choosing the algorithm. The signal is in three properties: weighted vs unweighted, presence of negative edges, and what answer is required (single shortest path, all pairs, MST, SCC).

7 · Three worked problems — Dijkstra with twists

Three problems that look different but reduce to "Dijkstra with a tweaked cost function". Each one is a senior-loop favourite; together they cover the bulk of "advanced shortest path" questions on LeetCode.

7a · LC 787 — Cheapest Flights Within K Stops

Problem. A network of n cities and flights[i] = [from, to, price]. Find the cheapest price from src to dst using at most K intermediate stops, or -1 if impossible.

Input:  n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
        src = 0, dst = 3, K = 1
Output: 700
Explanation: 0 -> 1 -> 3 costs 700 with 1 stop.
             0 -> 1 -> 2 -> 3 costs 400 but uses 2 stops (K+1=2 edges allowed, this is 3 edges).

The reframe: state isn't just "city" — it's (city, stops_used). Run Dijkstra on the product graph. Each heap entry is (cost, city, stops_so_far); relax a neighbour only if stops_so_far < K. The visited set is also keyed on (city, stops), not just city — the same city with fewer stops remaining might be worth revisiting.

func findCheapestPrice(n int, flights [][]int, src, dst, K int) int {
    // Build adjacency list
    graph := make(map[int][][2]int) // from -> [(to, price), ...]
    for _, f := range flights {
        graph[f[0]] = append(graph[f[0]], [2]int{f[1], f[2]})
    }

    // Heap: (cost, city, stops_used)
    // Use container/heap with a custom type; pseudocode here for clarity
    type State struct{ cost, city, stops int }
    pq := []State{{0, src, 0}}

    for len(pq) > 0 {
        // Pop minimum cost
        cur := pq[0]
        pq = pq[1:] // (real impl: heap.Pop)

        if cur.city == dst {
            return cur.cost
        }
        if cur.stops > K {
            continue // out of budget
        }
        for _, nb := range graph[cur.city] {
            next := State{cur.cost + nb[1], nb[0], cur.stops + 1}
            pq = append(pq, next) // (real impl: heap.Push)
        }
    }
    return -1
}

7b · LC 1631 — Path With Minimum Effort

Problem. A grid of heights. From the top-left to the bottom-right, find a path that minimises the maximum absolute height difference between two consecutive cells along the path.

Input:  heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: Path [1,3,5,3,5] has max consecutive diff of 2.
             Path [1,2,2,2,5] also valid; both have effort 2.

Two solutions, both common in interviews:

• Modified Dijkstra. The cost of a path isn't sum-of-edges — it's max-of-edges. Adjust the relaxation: new_effort = max(current_effort, abs(height[v] - height[u])). Otherwise everything is standard.
• Binary search on the answer. Binary-search the threshold T; the predicate is "can I reach the goal using only edges with diff ≤ T?", verified with BFS. O(log(max_diff) × V). Often slightly faster in practice than Dijkstra here.

func minimumEffortPath(heights [][]int) int {
    rows, cols := len(heights), len(heights[0])
    effort := make([][]int, rows)
    for i := range effort {
        effort[i] = make([]int, cols)
        for j := range effort[i] {
            effort[i][j] = 1 << 30 // +infinity
        }
    }
    effort[0][0] = 0

    // Min-heap of (effort, row, col)
    // pq.Push({0, 0, 0})

    dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    for /* pq not empty */ false {
        // cur := pq.Pop()
        // if cur.row == rows-1 && cur.col == cols-1 { return cur.effort }
        // if cur.effort > effort[cur.row][cur.col] { continue } // stale
        // for _, d := range dirs {
        //     nr, nc := cur.row+d[0], cur.col+d[1]
        //     if inside(nr, nc, rows, cols) {
        //         newEffort := max(cur.effort, abs(heights[nr][nc] - heights[cur.row][cur.col]))
        //         if newEffort < effort[nr][nc] {
        //             effort[nr][nc] = newEffort
        //             pq.Push({newEffort, nr, nc})
        //         }
        //     }
        // }
    }
    return effort[rows-1][cols-1]
}

7c · LC 778 — Swim in Rising Water (HARD)

Problem. An n × n grid where grid[r][c] is the elevation. At time t, the water level is t, and you can swim into a cell iff its elevation ≤ t. Find the minimum time to reach the bottom-right from the top-left.

Input:  grid = [[0,2],[1,3]]
Output: 3
Explanation: At time 0, only cell (0,0) is reachable.
             At time 1, cells (0,0) and (1,0) are reachable (elevations 0,1).
             At time 3, cell (1,1) becomes reachable (elevation 3). Answer = 3.

Same shape as LC 1631 but the cost function is max(t_so_far, grid[nr][nc]) instead of max(effort, abs(diff)). The answer is the minimum "max elevation along the path" from start to end. Dijkstra with the modified cost function. O(N² log N).

func swimInWater(grid [][]int) int {
    n := len(grid)
    visited := make([][]bool, n)
    for i := range visited {
        visited[i] = make([]bool, n)
    }

    // Min-heap of (time, row, col)
    // Start: (grid[0][0], 0, 0)

    dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    for /* pq not empty */ false {
        // cur := pq.Pop()
        // if visited[cur.row][cur.col] { continue }
        // visited[cur.row][cur.col] = true
        // if cur.row == n-1 && cur.col == n-1 { return cur.time }
        // for _, d := range dirs {
        //     nr, nc := cur.row+d[0], cur.col+d[1]
        //     if inside(nr, nc, n) && !visited[nr][nc] {
        //         pq.Push({max(cur.time, grid[nr][nc]), nr, nc})
        //     }
        // }
    }
    _ = dirs
    return -1
}

8 · How to solve hard graph problems step-by-step

Five questions to ask in order, every time. Most failed graph interviews fail at step 1 or 2 — picking the wrong algorithm or missing that the state is more than just the node ID.

1. Draw the graph. On paper or in your head, sketch a small instance. Is it weighted? Directed or undirected? Dense (E ≈ V²) or sparse (E ≈ V)? Connected, or potentially disconnected? These four properties pin down which family of algorithms is even applicable.
2. Identify the cost function. What are you minimising? Sum of edges (vanilla Dijkstra / Bellman-Ford). Max edge along the path (LC 1631-style). Count of edges (BFS). Sum subject to a count constraint (Bellman-Ford with rounds = K, or product-graph Dijkstra). Sum × something time-dependent (need to be careful — Dijkstra requires monotonicity).
3. Identify the state. Each "node" in your search graph isn't always just node_id. If the problem has a side constraint — fuel, K stops, time-of-day, must-visit set — the state is (node_id, side_state). The product graph has V × S effective nodes. Plan memory accordingly.
4. Match to algorithm. Weighted non-negative → Dijkstra (heap). Weighted with negatives → Bellman-Ford. Unweighted → BFS. All-pairs and small V → Floyd-Warshall. MST → Kruskal + DSU. SCC → Tarjan. State-augmented → product-graph Dijkstra or DP. Cost is max-of-edges → modified Dijkstra. Online edges with connectivity queries → union-find.
5. Verify on a 3-5 node example. Trace one iteration by hand. Confirm the heap pops the right node, the relaxation produces the right distance, the visited set is keyed correctly. This catches the "I forgot to make state part of the visited key" bug, which silently produces wrong answers on bigger inputs.

9 · Bellman-Ford in pictures

Bellman-Ford's mechanic is dead simple: relax every edge, |V| − 1 times. After the kth round, the distance to every node reachable in at most k edges is correct. After round |V| − 1, every shortest path (which can have at most |V| − 1 edges) is correct. One extra round; if anything still relaxes, you've found a negative cycle.

10 · Five-problem progression

11 · Real production stories — where these algorithms ship

One-line vignettes of how each algorithm shows up in real infrastructure. Worth name-dropping in interviews when the conversation drifts to "how does this apply in practice".

• Dijkstra at Google Maps. Bidirectional Dijkstra augmented with contraction hierarchies. Pre-process the road graph by adding "shortcut" edges that summarise common paths; query time drops from seconds to microseconds on continental-scale graphs (millions of nodes). The textbook algorithm is the foundation; ten years of engineering sits on top.
• OSPF / IS-IS routing protocols. Every interior gateway protocol on the planet runs Dijkstra over a link-state database. Each router floods its local view; everyone independently computes shortest paths to every other router. The protocol's data plane is the trickier part; the algorithm is just Dijkstra.
• Bellman-Ford in BGP / RIP. Distance-vector routing protocols use distributed Bellman-Ford — each router relaxes edges in its own table, sharing updates with neighbours. The "count to infinity" problem (slow convergence on link failures) is a Bellman-Ford pathology that link-state protocols (OSPF) avoid.
• Bellman-Ford for forex arbitrage. Currency-conversion graph; edge weight = −log(exchange rate). A negative cycle means an arbitrage opportunity exists (a cycle of conversions where you end up with more money than you started). Bellman-Ford's "if anything relaxes in round V, there's a negative cycle" check IS the arbitrage detector. Every FX trading desk has this running somewhere.
• MST in cluster networking. Spanning Tree Protocol (STP) — the ethernet protocol that prevents loops in switched networks — is a distributed MST. Each switch participates; the protocol converges on a unique spanning tree of the switch graph. Without STP, broadcast storms; with it, a guaranteed loop-free L2 topology.
• Tarjan SCC in compilers. Compilers compute SCCs of the call graph to find mutually-recursive function groups (which must be type-checked together, optimised together). Used in inliner heuristics, dead-code elimination across cycles, and recursive-definition processing.
• Topological sort in build systems. Bazel, Buck, ninja all compute a topological order of build targets. Independent targets in the DAG execute in parallel; the topological constraint guarantees no target builds before its dependencies. Cycle detection upfront catches misconfigurations.
• Max-flow / min-cut in image segmentation. The "graph cuts" technique in computer vision constructs a flow network where pixels are nodes, edges encode similarity, and a min-cut separates foreground from background. Used in Photoshop's magic-wand, medical imaging, and Adobe products' object isolation. Boykov-Kolmogorov is the standard implementation.

12 · Common pitfalls

• Using BFS on a weighted graph. BFS only finds the shortest path when edges are uniform. Wrong answer the moment weights differ.
• Dijkstra with negative weights. Also wrong, and silently so. Once a node is finalised, Dijkstra assumes no shorter path will ever appear — a negative edge breaks the invariant. Use Bellman-Ford. The bug is dangerous because Dijkstra terminates and produces some distance, just not the right one.
• Forgetting the visited / stale-entry check in Dijkstra. Correctness still holds — the algorithm finds the right distances — but you re-expand neighbours from outdated heap entries and performance degrades from O((V+E) log V) to something closer to O((V+E)² log V) on dense graphs. The if u in dist: continue line is the fix.
• Bellman-Ford needs one extra iteration to detect negative cycles. Run V−1 iterations to compute distances; run one more to see if anything still relaxes. If it does, a negative cycle is reachable.
• MST on a disconnected graph. No spanning tree exists. Prim will silently stop short of V−1 edges; Kruskal will exhaust the sorted edge list. Check for connectivity (or report a minimum spanning forest) explicitly.
• Confusing Prim with Kruskal. Both build the MST. Prim grows from a seed vertex outward using a heap of frontier edges. Kruskal sorts all edges by weight and unions endpoints with union-find, skipping edges that would form a cycle. Same answer, different shape.
• Off-by-one on K stops (LC 787). "At most K stops" means at most K+1 edges (a 1-stop journey is src → middle → dst, two edges). Many candidates write the loop bound as stops < K when it should be stops <= K for "edges used so far". Trace a 2-node, 1-stop case to verify.
• Not handling disconnected source. If the start node can't reach the target, the algorithm should return -1 or +infinity. Many implementations crash on max(distances) or return a garbage value when some nodes were never visited. Check explicitly.
• Storing the full graph when an edge list would do. Bellman-Ford only needs the edge list. Building an adjacency map for it is wasted work and an unnecessary indirection on hot iteration loops.
• Wrong relaxation order in DP-style Bellman-Ford (LC 787). The standard write-up uses a snapshot of the previous round's distances when relaxing in the current round. Using the in-progress distances allows multi-hop relaxation in one iteration and breaks the K-stops constraint. The fix: make a copy of dist at the start of each round, relax from the copy, write into dist.
• Comparison with floats. When the weights are real-valued (currency conversion, latency in ms), use absolute or relative tolerance when comparing distances. Strict equality bites when floating-point rounding nudges a tie one way.

13 · What to say in the interview

1. Name the algorithm explicitly. "Non-negative weights, so Dijkstra." "Negative edges, so Bellman-Ford." "All pairs and small V, so Floyd-Warshall." The interviewer wants to hear the name.
2. State the complexity up front. O((V + E) log V) for Dijkstra with a heap, O(V · E) for Bellman-Ford, O(V³) for Floyd-Warshall, O(E log E) for Kruskal, O(V + E) for Tarjan.
3. Mention when the algorithm falls short. "Dijkstra breaks on negative weights." "Bellman-Ford's the slow one but handles negatives and detects negative cycles." Showing you know the failure modes is half the answer.
4. Reference union-find for Kruskal. If you reach for Kruskal, mention that the cycle check is done with union-find — find-the-root, union-by-rank, near-constant amortised cost. It's the natural pairing.
5. For Tarjan, mention low-link values. The mechanism is a DFS that assigns each node a discovery index and a low-link value (the smallest index reachable via back-edges). Nodes with equal index and low-link are SCC roots.
6. Edge cases to mention. Disconnected graph (no MST, or report forest), single node, self-loops, parallel edges (keep the cheapest for MST), unreachable nodes in shortest-path output.

14 · Where this gets asked

15 · Try it yourself

Network Delay Time · LC 743

The canonical Dijkstra. Hint: heap of (dist, node), pop minimum, skip if already finalised, relax neighbours. Answer is the maximum of all finalised distances; return -1 if any node is unreachable.

Cheapest Flights Within K Stops · LC 787

Bellman-Ford or constrained Dijkstra. Hint: standard Bellman-Ford runs K+1 iterations, relaxing edges from a SNAPSHOT of the previous round's distances. The snapshot is critical — using current distances allows multi-hop relaxation in one iteration and breaks the K-stops constraint.

Min Cost to Connect All Points · LC 1584

MST on a complete graph. Hint: Kruskal — sort all n² edges by Manhattan distance, use DSU, pick the next edge if its endpoints are in different components. Stop when you've added n-1 edges.

Reconstruct Itinerary · LC 332

Hierholzer's algorithm for Eulerian path. Hint: from "JFK", DFS picking the smallest unused outgoing edge each time. Add to the path in POST-ORDER (after the recursive call returns). Reverse the path at the end.

Stretch — Critical Connections · LC 1192

Tarjan's bridge-finding. Hint: each node tracks disc[v] (discovery time) and low[v] (lowest discovery time reachable from subtree). An edge (u, v) is a bridge iff low[v] > disc[u]. The proof is short and worth working through.

Further reading

• CLRS — Chapters 23–25. The definitive treatment. Chapter 23 covers MST (Prim, Kruskal), 24 single-source shortest paths (Dijkstra, Bellman-Ford), 25 all-pairs (Floyd-Warshall, Johnson's). Worth working through once.
• Sedgewick & Wayne — Algorithms, Chapter 4. Cleaner code and good Java implementations of every algorithm here. Pairs well with the CLRS proofs.
• Adjacent: Union-find. The data structure Kruskal's MST runs on. Worth its own pattern — disjoint-set union with path compression and union-by-rank.
• Adjacent: BFS. The unweighted version of shortest path. Reach for BFS first; only fall back to Dijkstra when weights matter.
• Adjacent: DFS. The backbone of Tarjan's SCC and Kosaraju's algorithm. Understanding DFS recursion and the call stack is prerequisite to understanding low-link values.
• Semicolony: Dijkstra Pathfinding simulator. Watch Dijkstra and A* expand on a grid. Useful for building intuition about how the priority queue orders exploration.