L56 · Advanced Graphs

Series: LeetCode — From Basics to Interview-Ready · Session 56 / 65 · Phase 3 · Advanced & specialised

Why this session exists

Weighted graph algorithms have a reputation for being hard to remember. They are not, once you stop treating them as four separate algorithms and start seeing them as one algorithm with a swapped-out data structure.

BFS explores in order of hop count because a queue is FIFO. Replace the queue with a priority queue keyed on accumulated distance, and it explores in order of distance instead. That is Dijkstra. Nothing else changes structurally — you still pop a node, still look at its neighbours, still record where you came from. If you can write BFS cold, you are about six lines away from Dijkstra.

Prim's algorithm is the same skeleton again with the priority key changed from "distance from source" to "edge weight alone". Kruskal is the odd one out — it sorts edges and unions components — but it is short and it reuses the union-find you already know.

Bellman-Ford is the one that exists because Dijkstra has a real limitation: it assumes that once you pop a node, its distance is final. With negative edge weights that assumption is false, and Dijkstra returns wrong answers with total confidence. Knowing precisely where that boundary sits is worth more than being able to write either algorithm.

Blank-file warm-up

Five minutes, empty file: the heap-based Dijkstra skeleton.

Import the heap, initialise the distance table, push the source, then the pop-relax-push loop. About twelve lines.

The specific thing to check: did you include the stale-entry guard? The standard heap Dijkstra never decreases a key in place — it pushes duplicates and discards outdated pops. If your loop has no if d > dist[u]: continue line, it still produces correct answers but does redundant work, and more importantly it means you have memorised the code without understanding why the duplicates are there.

Pattern anatomy

The shape: a weighted graph, and you want either the cheapest path from one node to others, or the cheapest set of edges connecting everything.

The invariant Dijkstra maintains: when a node is popped from the heap, its recorded distance is final and optimal. This holds because all edge weights are non-negative — any alternative route to that node would have to pass through some node still in the heap with a distance at least as large, and adding more non-negative edges cannot make it smaller. That one sentence is the correctness proof and also, read carefully, the statement of exactly when Dijkstra breaks.

import heapq
 
def dijkstra(n, adj, src):
    """adj[u] = list of (v, weight). Returns dist list, INF for unreachable."""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                      # stale entry: a better path was already finalised
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Bellman-Ford drops the greedy assumption entirely. It relaxes every edge, n-1 times, because any shortest path has at most n-1 edges and each full pass extends the frontier by at least one edge:

def bellman_ford(n, edges, src):
    """edges = list of (u, v, w). Handles negative weights."""
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                          # early exit: nothing improved
    # one more pass detects a negative cycle
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None                    # negative cycle reachable from src
    return dist

Prim grows one tree outward, always taking the cheapest edge leaving it:

def prim(n, adj):
    """Total weight of a minimum spanning tree, or None if disconnected."""
    seen = [False] * n
    pq = [(0, 0)]                          # (edge weight, node)
    total = count = 0
    while pq and count < n:
        w, u = heapq.heappop(pq)
        if seen[u]:
            continue
        seen[u] = True
        total += w
        count += 1
        for v, wt in adj[u]:
            if not seen[v]:
                heapq.heappush(pq, (wt, v))
    return total if count == n else None

Kruskal sorts every edge and adds it unless it would close a cycle:

def kruskal(n, edges):
    """edges = list of (w, u, v)."""
    parent = list(range(n))
 
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x
 
    total = used = 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
            used += 1
            if used == n - 1:
                break
    return total if used == n - 1 else None

Look at Prim next to Dijkstra. The only difference is heappush((wt, v)) versus heappush((d + w, v)) — Prim keys on the edge alone, Dijkstra on the accumulated path. That is genuinely the whole distinction, and remembering it means you only have to remember one algorithm.

The cue

1. "Minimum time / cost / delay for a signal to reach all nodes" with non-negative weights. Dijkstra from the source; the answer is the maximum finalised distance.
2. Weighted graph, single source, and the word "shortest". Dijkstra unless something in the constraints says otherwise.
3. Negative weights appear anywhere in the constraints. Dijkstra is disqualified. Bellman-Ford, or SPFA if you want the queue-based variant.
4. "At most K stops / at most K edges / exactly K moves". This is the tell people miss. A hop limit turns the state from "node" into "(node, hops used)". Bellman-Ford with exactly K+1 relaxation rounds is the cleanest expression, because each round corresponds to one additional edge.
5. "Connect all points / all nodes at minimum total cost", with no source and no path — just connectivity. That is a minimum spanning tree. Prim if the graph is dense or given as coordinates; Kruskal if you are handed an edge list.
6. A grid where movement costs vary — "minimum effort path", "swim in rising water". Grids are implicit graphs; Dijkstra applies directly with neighbours computed rather than stored.

The distinction between tell 1 and tell 5 is worth being crisp about: shortest-path minimises the cost of one route, MST minimises the total cost of keeping everything connected. An MST does not contain shortest paths, and a shortest-path tree is usually not minimal in total weight.

Guided solve

Network Delay Time. A directed weighted graph, n nodes, a source k. Return the time for a signal to reach every node, or −1 if some node is unreachable.

Parse what is being asked. A signal propagates along all edges simultaneously, so a node receives it at the time of its shortest path from the source. Every node has received it when the slowest of those shortest paths completes. So: run single-source shortest paths, take the maximum, and return −1 if any distance is still infinite.

Weights are positive travel times, so Dijkstra applies.

import heapq
from collections import defaultdict
 
def networkDelayTime(times, n, k):
    adj = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))
 
    dist = {}
    pq = [(0, k)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in dist:
            continue                 # already finalised — this is a stale entry
        dist[u] = d
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(pq, (d + w, v))
 
    return max(dist.values()) if len(dist) == n else -1

Two implementation notes worth saying aloud.

First, the nodes here are 1-indexed, which is why a dict beats a list — it sidesteps the off-by-one entirely. In an interview, choosing the data structure that removes a class of bug is itself a signal.

Second, the if u in dist: continue guard replaces the d > dist[u] guard from the template. They are the same idea: a node can be pushed several times with different tentative distances, and only the first pop is authoritative because the heap hands them back in increasing order. We never delete the stale entries; we ignore them on the way out. Decrease-key is theoretically cleaner and practically worse — Python's heapq does not support it, and the lazy-deletion version is shorter and faster in practice.

Verify by hand on the two-node case: times = [[1,2,1]], n = 2, k = 1. Distances are {1: 0, 2: 1}, max is 1. Then check k = 2: only node 2 is reachable, len(dist) == 1 != 2, returns −1. Both edge cases in ten seconds.

Solo timed

Fifteen minutes each.

• Cheapest Flights Within K Stops — the hop limit is the whole problem. Think about what a single Bellman-Ford relaxation round means in terms of edge count, and be careful that one round does not cascade into using more edges than it should. There is a one-line fix involving a snapshot of the previous round.
• Min Cost to Connect All Points — no edge list is given, only coordinates. That makes the graph complete with n² edges. Consider which MST algorithm handles a dense implicit graph better before you start writing.

Common failure modes

Using Dijkstra with negative weights. It does not error, it does not warn, it returns a plausible wrong answer. Once a node is popped its distance is frozen, and a negative edge discovered later can never correct it. Scan the constraints for negative values before you commit.

Forgetting the stale-entry guard. Without if d > dist[u]: continue, you re-expand nodes that are already final. The answers stay correct but the work grows, and on a dense graph it is the difference between passing and timing out.

Bellman-Ford cascading within a round. If you relax edges in place, a distance updated earlier in the same pass can be used again later in that same pass, effectively using more than one extra edge per round. For plain shortest paths this is harmless — it converges faster. For a bounded-hop problem it is fatal. Snapshot the distance array at the start of each round and read from the snapshot.

Comparing MST algorithms to shortest-path ones. Prim's tree minimises total edge weight, not the path from any particular node. Using an MST to answer a shortest-path question produces confidently wrong answers on almost every non-trivial graph.

Forgetting the disconnected case. Both MST algorithms must check that they actually connected everything — used == n - 1 edges for Kruskal, count == n nodes for Prim. A disconnected graph has no spanning tree, and silently returning a partial forest's weight is a wrong answer that looks reasonable.

Complexity

Dijkstra with a binary heap: O(E log V). Each edge can cause at most one push, so the heap holds at most E entries and each pop or push is logarithmic. Space O(V + E). With a Fibonacci heap it is O(E + V log V) in theory — mention it, do not implement it.

Bellman-Ford: O(V·E). V-1 rounds, each touching every edge. Space O(V). The early-exit on an unchanged round often makes it much faster in practice, but the worst case stands.

Prim with a heap: O(E log V), same argument as Dijkstra. Better on dense graphs, where Kruskal's sort dominates.

Kruskal: O(E log E) for the sort, plus near-constant amortised union-find operations. Better when the edge list is already available and sparse.

Min Cost to Connect All Points with n coordinates: the implicit graph has n²/2 edges, so Kruskal's sort is O(n² log n) while Prim is O(n²) with a simple array-based minimum. On a dense implicit graph Prim wins.

Spaced queue

Re-solve what is due before new material. Status ladder:

• cold — clean and unaided → 60 days
• warm — solved with a stumble → 21 days
• hint — needed a nudge → 7 days
• failed — no working solution → 2 days, then 7 days

Dijkstra should be at cold by now if the earlier BFS sessions consolidated. If it is not, the problem is usually the heap mechanics rather than the graph reasoning — practise the pop-relax-push loop rather than re-reading the theory.