Advanced Graphs
Shortest paths when edges have costs
Breadth-first search with a heap instead of a queue, and a precise reason why that works.
Key idea
Where breadth-first search fails
Breadth-first search is correct because the first arrival at a node is by the fewest edges, and with equal edge costs fewest edges means cheapest. Once edges have different costs those two stop being the same thing.
A path of one expensive edge can cost more than a path of three cheap ones. The queue reaches the one-edge path first and records it as the answer, which is simply wrong.
Why it works
Take the cheapest unfinished node, not the earliest
The repair is to change what comes out next. Instead of a queue handing back the earliest arrival, use a heap handing back the smallest known distance.
The invariant then becomes: when a node is popped, its recorded distance is final. Nothing still in the heap can improve it, because everything in the heap is at least that far away already and every edge adds a non-negative amount.
That sentence is the whole correctness argument, and it names its own precondition: edge costs must be non-negative. With a negative edge, a longer route could get cheaper later, and the guarantee collapses.
Gotcha
Skip stale entries, do not try to remove them
The same node can be pushed several times with different costs, because a better route may be discovered after a worse one was already queued. A heap cannot remove or update the old entry.
So do not try. Check on pop whether the node is already finalized and skip it if so. This is the lazy deletion from Unit 9, and it is the standard way to write this algorithm in Python.
Leaving that check out is the most common bug here. It does not give a wrong distance, since the first pop of a node is the smallest, and it does cause the node's neighbors to be reprocessed repeatedly.
Gotcha
Marking visited on push is wrong here
In plain breadth-first search, marking a node as seen when it is pushed is a good habit. In this algorithm it is a bug.
Marking on push commits to the first cost discovered for a node, which is exactly the mistake the whole algorithm exists to avoid. Finalization has to happen on pop, when the heap guarantees no cheaper route remains.
If a weighted shortest-path solution returns answers that are correct on some graphs and too large on others, this is almost always why.
Key idea
A variant: cost that is not a sum
Some problems ask for the path minimizing the largest edge along it rather than the total. The algorithm is unchanged except for how a neighbor's tentative cost is computed: take the maximum of the current cost and the edge weight instead of the sum.
The correctness argument survives because a maximum is also non-decreasing along a path, which is the only property it actually relied on. Recognizing that the argument depends on non-decreasing accumulation rather than specifically on addition is what lets you adapt this rather than memorize it.
Cost
Cost
Each edge can cause one push, and each push can cause one pop, so O(edges times log edges) with a binary heap. That is usually written O(E log V), since the number of entries is bounded by the edges and log of the edge count is within a constant factor of log of the node count.
Space is the heap plus the distance map, so O(edges plus nodes). Quote the form with both sizes named.
Trace the finalization order
Run the algorithm from A on edges A to C costing 10, A to B costing 1, B to C costing 1. For each pop give the node finalized and its final cost. Ignore stale pops that get skipped.
This activity type is not wired up yet.
Two shortest-path variants
cheapest_total returns the minimum total cost from a start to every reachable node. lowest_ceiling returns, for every reachable node, the smallest possible value of the largest edge on a path to it. Both take an adjacency map of node to a list of (neighbor, weight).
Tests
graph = {
"A": [("B", 1), ("C", 10)],
"B": [("C", 1)],
"C": [],
"D": [],
}
print(cheapest_total(graph, "A"))
print(lowest_ceiling(graph, "A"))
print(cheapest_total(graph, "D"))Output
Run the tests when you are ready.
Network Delay Time
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Swim In Rising Water
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.