Shortest paths and MST
What is the cheapest way through a weighted graph?
The ₹10 shortcut
Merchants are paid through partner banks, and a payout can hop between banks before it lands. Every hop charges a fee. The first router runs the BFS from Unit 14 and picks the route with the fewest hops.
For one merchant that is the direct transfer: one hop, ₹10. There is also a route through two other banks that costs ₹1, then ₹2, then ₹1. That is three hops and ₹4. Work out the waste: at 200,000 payouts like that a month, the fewest-hops rule pays ₹6 too much each time, which is ₹12 lakh a month.
The next idea is to list every route and take the cheapest. With 14 banks that can all reach each other, there are about 1.3 billion simple routes between two of them, and the router has 50 milliseconds.
So the fewest hops is the wrong measure, and checking every route is far too slow. What you want is a way to become certain of the cheapest cost to one bank at a time, so that you never have to look at that bank again.
Pause and predict Fees are never negative. Call a bank settled once its cheapest cost is known for certain. Among the banks not yet settled, take the one with the cheapest route found so far. Can some other route to it still turn out cheaper?
The closest node left is already final
BFS finds the route with the fewest edges, which is the cheapest route only when every edge costs the same. Once edges have different weights, that fails: a route of three edges costing 1 each beats one edge costing 10. Trying every route takes exponential time.
Dijkstra grows a set of settled nodes whose distance is known for certain. Every other node has a tentative distance, the best route found so far. Each step takes the unsettled node with the smallest tentative distance, settles it, and relaxes its edges: for each edge from u to v with weight w, if dist[u] + w is smaller than dist[v], the route through u is better, so dist[v] is lowered to dist[u] + w.
A min-heap holds the tentative distances, as entries (d, node). A heap cannot lower an entry's value in place, so when a shorter route to v turns up, push a new entry and leave the old one where it is. The old one is now a stale entry: when it comes out, its d is larger than dist[v], and you skip it. Each edge pushes at most one entry, so the run costs O(E log E).
Where it breaks: one negative edge
Pause and predict A to B costs 2, A to C costs 3, C to B costs -2. Dijkstra pops B at 2 and calls it final. What is the true shortest distance to B?
A version that keeps a visited set never reopens B, so it answers 2, which is wrong. The template, which only skips stale entries, lowers B again when C is popped and pops B a second time. It gets the right answer here, but each node is no longer popped only once, and the running-time guarantee goes with it: on bad graphs, nodes are popped over and over. With a negative cycle there is no shortest distance at all. For negative weights, use Bellman-Ford.
The same loop, other costs
Pause and predict Suppose a route's cost is its worst single step instead of the sum of its steps. Does the same loop still find the cheapest route?
If every weight is 0 or 1, the heap only ever holds two distances, d and d + 1. A deque keeps them in order with no heap: push a node reached by an edge of weight 0 to the front, since it has the same distance as the node just popped, and a node reached by an edge of weight 1 to the back. That is 0-1 BFS, O(V + E).
When the limit is on edges
Cheapest Flights Within K Stops allows at most k + 1 flights. Now a more expensive route with fewer stops may be the only one that fits, and Dijkstra, which keeps one best price per city, throws it away. Bellman-Ford limits the number of edges by working in rounds. Each round relaxes every edge once, so after round i, price[v] is the cheapest route to v that uses at most i edges. Run k + 1 rounds.
That holds only if round i reads the prices from the end of round i - 1. If a round writes into the same array it reads from, a price set early in the round can be used by another flight later in the same round, so one round can add more than one flight. With A to B 100, B to C 100, A to C 500 and k = 0, an in-place round finds 200, a route with one stop. The answer is 500. So copy the prices at the start of every round.
Connecting everything: a spanning tree
Min Cost to Connect All Points has no source. It asks for the cheapest set of edges that joins every node, which is called a minimum spanning tree. Prim's algorithm runs the same loop from any starting node, with one change: the key of a node is the cost of the cheapest single edge from the tree to it, not the length of a path.
Kruskal's algorithm uses the same property in a different way: sort all the edges by cost, and add each edge that joins two different components, which you check with union-find.
A maps service answers "fastest route" with this loop over road junctions, usually in a form called A*, which adds to each key a straight-line estimate of the distance still to go, so that fewer junctions need to be settled.
How to recognise it
The main signal is a word like "minimum cost", "cheapest" or "fastest" on a graph whose edges have weights. Then read the details: the kind of weight and the kind of limit decide which loop to use.
Pause and predict The statement says every weight is 0 or 1. Do you need a heap?
Four that only look like it
- When every edge costs the same, the cheapest route is the one with the fewest edges, and plain BFS finds it (see BFS and DFS). Dijkstra would also work, but more slowly.
- When the only question is "are these connected?", with no costs, use union-find or a traversal.
- When the graph is a DAG (a directed graph with no cycle, such as tasks and their dependencies), relax the edges in topological order. That takes O(V + E) and works even with negative weights or for longest paths.
- When you only need the k best items of a list, a heap alone does it, in heaps. In this unit the heap is a tool inside a graph search.
Where it bites
Pause and predict Java: prices[u] = Integer.MAX_VALUE (unreached) and w = 100. Is prices[u] + w < 500?
- Dijkstra with negative weights. A popped node's distance is no longer final. Check the constraints for the word "negative" before you reach for the heap.
- Plain Dijkstra with a stop limit. Keeping one price per city throws away the more expensive route with fewer stops. Use Bellman-Ford rounds, or make the number of stops part of each node's state.
- Bellman-Ford in place when the number of edges is limited. Copy the prices at the start of each round.
- Marking a node visited when it is pushed, as in BFS. A node can be reached first by a worse route, so its distance is final only when it is popped.
- Using Prim's key in Dijkstra, or Dijkstra's key in Prim. Dijkstra's key is a path length; Prim's key is the cost of one edge.
- The start of a minimax path. In Swim in Rising Water the start cell's own height counts, while in Path With Minimum Effort the start costs 0.