4.21.0 — Advanced Graphs: The Pattern

Recognition cue. The edges have weights. Or the question is "connect everything cheaply", "the cheapest route", or "use every edge exactly once".

Choosing the algorithm

This is the whole chapter. Read the question, pick from this table, and the implementation is routine.

the question	the tool	why
shortest path, all edges equal	BFS	first arrival is optimal
shortest path, non-negative weights	Dijkstra	closest unfinished node can be finalised
shortest path, negative weights or a hop limit	Bellman-Ford	counts edges in rounds
shortest path between all pairs, small graph	Floyd-Warshall	O(V^3), three loops
connect everything cheaply	MST — Prim's or Kruskal's	a tree, not a path
use every edge once	Hierholzer (Eulerian)	linear
use every node once	Hamiltonian	NP-hard — say so
ordering, dependencies, cycle check	topological sort	4.20.8
"are these connected", edges arriving	union-find	incremental

Two distinctions do most of the work.

MST is not shortest path. MST minimises the total cost of connecting everything; shortest path minimises the cost from one source to each node. The path between two nodes in an MST is usually not the shortest path between them.

Eulerian is not Hamiltonian. Every edge once is linear. Every node once is NP-hard. They sound alike and could not be further apart.

Dijkstra, and the one assumption

import heapq
dist = {}
heap = [(0, start)]
while heap:
    cost, node = heapq.heappop(heap)
    if node in dist: continue          # lazy deletion — stale entry
    dist[node] = cost                  # first pop IS the shortest
    for nei, w in adj[node]:
        if nei not in dist:
            heapq.heappush(heap, (cost + w, nei))

Why finalising is safe: with non-negative weights, any alternative route to the closest unfinished node must pass through another unfinished node, which is already at least as far, and adding a non-negative edge cannot improve it.

That is exactly what negative weights destroy, and it is the answer to the most common follow-up.

Lazy deletion — the if node in dist: continue — exists because a heap cannot update a stored priority. Push duplicates and skip the stale ones.

The trap: adding a constant to every weight to remove negatives does not work. It penalises paths with more edges, so the shortest path can change.

The three substitutions worth knowing

Dijkstra does not require addition. It requires that extending a path never improves it. So:

• cost + weight → shortest sum (the usual case)
• max(cost, weight) → smallest maximum — 4.21.4
• cost × probability with a max-heap → most likely path

The six problems

#	Problem	Tool
4.21.1	Reconstruct Itinerary	Hierholzer — record on the way out, reverse
4.21.2	Min Cost to Connect All Points	MST — Prim's, because the graph is dense
4.21.3	Network Delay Time	Dijkstra, then take the maximum
4.21.4	Swim in Rising Water	Dijkstra with max instead of +
4.21.5	Alien Dictionary	Build the graph, then topological sort
4.21.6	Cheapest Flights Within K Stops	Bellman-Ford — Dijkstra is wrong here

Prim's or Kruskal's

Prim's grows one tree, using a heap of frontier edges. Better on dense graphs, and the only sensible choice when the edges are implicit.

Kruskal's sorts all edges and adds any that join two components, using union-find. Natural when the edges are given explicitly. Stop after n − 1 successful unions.

Both are greedy, and both are justified by the cut property: the cheapest edge crossing any split of the nodes belongs to some minimum spanning tree.

What the interviewer will push on

"Why is Dijkstra safe here?" Non-negative weights. Give the finalisation argument.

"What if a weight were negative?" The argument fails; use Bellman-Ford. And no, adding a constant does not fix it.

"Why does Dijkstra fail with a hop limit?" A cheaper route may use too many hops. Either count rounds with Bellman-Ford, or put the hop count into the state.

"MST or shortest path?" Connect everything versus travel from a source. They are different trees.

"Eulerian or Hamiltonian?" Every edge once is linear; every node once is NP-hard.

"What are the duplicate heap entries?" Lazy deletion.

One thing to volunteer: state the assumption your algorithm needs before you write it. "All weights are non-negative, so Dijkstra applies." It answers the next two questions in advance.

Recall

• MST ≠ shortest path. MST connects everything cheaply; shortest path travels from a source. Different trees.
• Eulerian (every edge once) is linear. Hamiltonian (every node once) is NP-hard.
• Dijkstra finalises the closest unfinished node, and that is valid only for non-negative weights.
• Adding a constant to remove negative weights changes the answer — it penalises longer paths.
• A hop limit breaks Dijkstra. Use Bellman-Ford, whose rounds count edges, and snapshot the distances each round or several edges chain in one round.
• Dijkstra works for any cost that never improves when extended: +, max, and multiplying probabilities.
• Lazy deletion — push duplicates, skip stale pops — because a heap cannot update a priority.
• Prim's for dense or implicit graphs, Kruskal's for explicit edge lists. Both justified by the cut property. Stop after n − 1 edges.
• Hierholzer: walk until stuck, record on the way out, reverse at the end.

Next: 4.21.1 Reconstruct Itinerary — the Eulerian path, and the one problem here where getting stuck is not a mistake.