Advanced Graphs

Review boundary and corrected contracts

Reviewed Dijkstra nonnegative-edge finality, Bellman–Ford reachable negative-cycle test and MST cut/exchange property. The lazy re-relaxing Dijkstra variant can revisit vertices on negative edges: its proof/bound fail, not every example answer. Kruskal now uses union by size plus halving. Empty-graph MST weight is zero; graph model excludes invalid endpoints.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Reconstruct heap-based Dijkstra from a blank file, know exactly when it breaks and what replaces it, and be able to build a minimum spanning tree two ways.

Series: LeetCode — From Basics to Production-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 hop-count order using a FIFO queue. Dijkstra chooses the smallest accumulated-distance candidate with a priority queue, relaxes edges when a cheaper route is found, and discards stale entries. The frontier loop is familiar, but first discovery is no longer enough to settle a node: on edges A→B=10, A→C=1 and C→B=1, B must improve from 10 to 2. Replacing the queue without replacing BFS’s discovery-time visited rule would be wrong.

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 useful when negative edges invalidate Dijkstra’s settled-distance proof. Distinguish the two displayed heap variants: the template can re-relax an already popped vertex, whereas Network Delay Time freezes its first pop. On negative-edge graphs they can behave differently; neither retains the nonnegative-edge Dijkstra guarantee. A reachable negative cycle also makes distances to its descendants unbounded below.

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 with its current best distance (not a stale entry), that distance is final and optimal under nonnegative weights. 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 distance has already been discovered
        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 relaxes all edges up to n−1 times. If no reachable negative cycle exists, a shortest route can be chosen simple and thus has at most n−1 edges. After j passes, every shortest route needing at most j edges has been accounted for; in-place relaxation may propagate farther within one pass. An additional improving edge after n−1 passes witnesses a reachable negative cycle.

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

Dijkstra and Bellman-Ford answered a route question: how cheaply can we reach each node from a source? For the next two algorithms, switch to an undirected graph and a network question: which edges connect every node with the smallest total construction cost? A cheap connecting network need not give the shortest individual routes. Prim builds that network as one growing tree, 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)."""
    if n == 0:
        return 0
    parent = list(range(n))
    size = [1] * 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:
            if size[ru] > size[rv]:
                ru, rv = rv, ru
            parent[ru] = rv
            size[rv] += size[ru]
            total += w
            used += 1
            if used == n - 1:
                break
    return total if used == n - 1 else None

Look at Prim next to Dijkstra. The visible heap-key difference is heappush((wt, v)) versus heappush((d + w, v)) — Prim keys on the edge alone, Dijkstra on the accumulated path. Tie that code difference to what becomes final: Prim accepts a connection into the growing tree, whereas Dijkstra settles a source-to-node distance. Their loops look similar because both choose the cheapest frontier candidate, but the candidates represent different objectives. Carry that distinction into the cues below rather than treating the algorithms as interchangeable.

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". Track both node and hop count. At most K intermediate stops permits K+1 edges: use K+1 snapshot-based rounds retaining shorter paths. At most K edges uses K rounds. Exactly K edges also uses K rounds, but initialise each new distance array to infinity rather than carrying shorter paths forward.
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. Ordinary shortest paths add weights. Minimum Effort Path instead extends a label by max(current_effort, edge_effort); Swim in Rising Water similarly uses a maximum elevation. These monotone bottleneck costs support a Dijkstra-style finality proof, but require changing d + w, not simply changing the neighbour generator.

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 need not give shortest source-to-node routes, and a shortest-path tree need not minimise total tree weight; some graphs, such as an input that is already a tree, satisfy both.

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. Under a tight review, choosing the data structure that removes a class of bug is itself a signal.

Second, the finalized-set guard and the template’s stale-distance guard both avoid redundant work under the nonnegative-weight contract, but are not identical on negative edges. heapq has no built-in decrease-key operation; pushing revised entries avoids maintaining an index map. That is a simplicity tradeoff, not a universal speed comparison.

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 a nonnegative-edge proof on negative edges. The finalized-set variant may freeze a wrong answer. The displayed re-relaxing template can repair it later, but loses the standard bound and may not terminate on a reachable negative cycle. Check the contract rather than assuming every negative edge makes every implementation return an incorrect value.

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 and Kruskal minimise total selected edge weight, not each source-to-node route. They can coincide on some inputs, but substituting one objective for the other is unjustified without a proof.

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.

Myth: Negative edges matter only when they form a negative cycle.

Why: A negative edge alone can invalidate first-pop finality in an acyclic graph. A reachable negative cycle is a different obstruction: descendants of that cycle have no finite shortest distance, while other vertices may still have finite answers. The Bellman–Ford API here returns None if it detects any such reachable cycle rather than classifying each affected vertex.

Steps 1: BFS visits nodes in increasing order of hop count because a FIFO queue returns the earliest-inserted node, and every edge costs exactly one hop.

Steps 2: Because the ordering property is what makes BFS correct, generalising to weighted edges requires a structure that returns the smallest accumulated cost rather than the earliest insertion.

Steps 3: Because a binary heap returns the minimum key in O(log n), substituting it for the queue preserves the ordering property with weights.

Steps 4: Because all weights are non-negative, the first time a node is popped its distance cannot be improved — any other route goes through a node with an equal or larger key plus additional non-negative edges.

Steps 5: Negative edges invalidate this proof, not necessarily the answer of every heap implementation on every input. A settled-set algorithm cannot revisit an early choice; the template above can re-relax it.

Steps 6: Use A→B cost 1, A→C cost 5, C→B cost −10 to separate the variants. A finalized-set implementation freezes B at 1 before C is popped, although the true distance is −5. The displayed re-relaxing template later updates B to −5. The earlier proposed example A→B=5, A→C=1, C→B=−10 does not distinguish them: C is popped first and both find −9.

Picture: Water spreading from a source through pipes of different lengths. BFS is water where every pipe is one metre — the wavefront is a circle of hops. Dijkstra is water where pipes vary — the wavefront is a circle of actual distance, and the heap is just the schedule of which pipe fills next.

Trigger: Fires whenever you have written BFS and then notice the edges carry weights.

Name: Dijkstra with a binary heap

Gain: O((V + E) log(V + E)), fast in practice, and structurally identical to BFS so it is cheap to remember

Cost: Requires non-negative weights, full stop. Cannot express hop limits without adding a dimension to the state.

Name: Bellman-Ford

Gain: Handles negative weights, detects negative cycles, and its round structure maps directly onto 'at most K edges' constraints

Cost: O(V·E) relaxations in the worst case. The runtime ratio to Dijkstra depends on graph density and the implementation; there is no fixed tenfold factor.

Nonnegative weights support Dijkstra. Hop bounds require a state containing both vertex and hops, or snapshot-based bounded Bellman–Ford rounds. Negative edges can also be solved by topological relaxation on a DAG; Bellman–Ford is not the only alternative.

Why the MST choices are safe

Take any cut separating a current tree/component from the other vertices, with no already selected edge crossing it. Let e be a minimum-weight edge across that cut. If an MST consistent with the selected edges omits e, adding e forms a cycle. The cycle crosses the cut again through some edge f; by minimality, weight(e) is at most weight(f). Removing f restores a spanning tree without increasing its weight or removing a selected edge. Thus some MST contains the next choice. Prim uses the cut around its growing tree; Kruskal uses a current component cut when it accepts the lightest edge joining two components. Ties are safe and negative edge weights are allowed for MSTs. This exchange argument, not the shortest-path finality proof, justifies both algorithms.

Complexity

Dijkstra with a binary heap: O((V + E) log(V + E)). 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((V + E) log(V + E)) time and O(V + E) auxiliary space for lazy candidates. This heap implementation does not gain an O(V²) dense-graph bound merely by being Prim; that requires the array-based minimum-selection variant.

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 undirected complete graph has n(n−1)/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.

Self-check (answer follows each question).

Q: What single line converts BFS into Dijkstra, structurally?

A: Replace FIFO frontier order with a priority queue keyed on accumulated distance, and use relaxation plus stale-entry handling rather than BFS’s first-discovery visited rule. The analogy is the frontier discipline; blindly changing one line in arbitrary BFS code is not sufficient.

Q: Why does the standard heap Dijkstra push duplicate entries instead of decreasing keys?

A: heapq has no direct decrease-key operation. Push an improved tentative distance and skip a pop if its stored key exceeds the current best. Under nonnegative weights the first current-best pop settles that node. An indexed heap is another valid design; no universal runtime comparison is implied.

Q: State precisely why Dijkstra requires non-negative weights.

A: First-current-pop finality relies on nonnegative path extensions: a route through an unsettled node cannot become cheaper by adding more edges. Negative weights invalidate that proof. A finalized-set variant never revisits its frozen distance; the displayed template can revisit and therefore needs a separate analysis outside the contract.

Q: How does 'at most K stops' map onto Bellman-Ford?

A: K stops permits at most K+1 edges. Run K+1 rounds, reading only the previous snapshot and initially copying its distances to retain shorter routes. Each round adds at most one edge to an already represented path; in-place updates can cascade and violate the bound.

Q: How do Prim and Dijkstra differ in code?

A: Dijkstra candidates carry accumulated path cost and use relaxation/stale-distance checks; Prim candidates carry a crossing edge’s own weight and use membership in the growing tree. Their goals and acceptance state differ as well as the heap key. Prim’s minimum crossing edge is safe by the cut/exchange argument below.

Q: Johnson's algorithm computes all-pairs shortest paths on a graph with negative edges faster than running Bellman-Ford from every node. What is the key idea?

A: Assuming no negative cycle anywhere, add a virtual source with zero-weight edges to every vertex and run Bellman–Ford for potentials h(v). Then w′(u,v) = w(u,v) + h(u) − h(v) is nonnegative by the shortest-path inequalities. Along a path from s to t the potentials telescope to h(s)−h(t), preserving path order. After Dijkstra, recover d(s,t) = d′(s,t) − h(s) + h(t). Reject the graph if the virtual-source run detects a negative cycle; speed depends on graph density and heap choice.

Stretch: true

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.

• Dijkstra shares BFS’s frontier idea but uses accumulated costs, relaxation and stale-entry handling. Its standard finality proof requires nonnegative edges.

• Negative edges invalidate Dijkstra’s standard proof/bound. A finalized-set implementation may be wrong; a re-relaxing implementation can repair some cases but is not certified by that proof.

• 'At most K stops' means bounded edge count, which means Bellman-Ford rounds with a per-round snapshot.

• Prim keys candidates by crossing-edge weight and accepts connections into a growing tree; Dijkstra keys by path cost and settles distances. Similar heaps do not make the objectives interchangeable.

• MST and shortest-path solve different problems. An MST contains no guarantee about any individual path.

• Always check the connectivity condition on MST code — n−1 edges for Kruskal, n nodes for Prim — or a disconnected graph returns a wrong-looking-right answer.

Corrective source notes

• Dijkstra - finding shortest paths from given vertex - Algorithms for Competitive Programming — The standard Dijkstra correctness argument assumes nonnegative edge weights. Checked 2026-10-07.
• Dijkstra on sparse graphs - Algorithms for Competitive Programming — Lazy heaps can retain stale distance entries, which must be skipped. Checked 2026-10-07.
• Bellman-Ford - finding shortest paths with negative weights - Algorithms for Competitive Programming — Bellman–Ford supports negative edges and can be modified to detect negative cycles; a cycle can make some shortest distances undefined. Checked 2026-10-07.
• Minimum Spanning Tree - Prim's Algorithm - Algorithms for Competitive Programming — Prim constructs a minimum spanning tree by adding a minimum crossing edge. Checked 2026-10-07.
• Minimum Spanning Tree - Kruskal with Disjoint Set Union - Algorithms for Competitive Programming — Kruskal can use DSU with union by rank and path compression to reject cycle-forming edges. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.