Dijkstra's Algorithm as a Spreading Frontier

Dijkstra's algorithm finds the cheapest route from one source to every node in a graph. The picture to keep is a filled region that spreads outward, with the edges crossing its boundary forming a live frontier. Here are six nodes. S is the source, and A, B, C, D and E are the other places. The gray connections are weighted edges. Their numbers measure cost, so a path is cheap when the sum of its edge weights is small. The weights are four, two, one, five, eight, ten, two again, six, and three. Every one is non-negative. That condition will carry the proof. This blue patch around S is the settled region we will grow. The two yellow edges leaving it are the frontier. Keep that boundary alive in your eye while the numbers decide which node the patch reaches next. First see why counting edges is not enough. Start at S, then B, then D, then E. This route uses only three edges. The three-hop route pays two, ten, and three. Together those weights total fifteen. The other route goes S, B, A, C, D, E. Its five weights are two, one, five, two, and three. Together they total thirteen. Fifteen is greater than thirteen. More hops can cost less, so every decision must use the accumulated weights rather than the hop count. Each node carries a tentative distance: the cheapest route found so far. Unreached nodes have no number yet. The source is different. Reaching S from S costs zero, so zero is final from the start. Relaxation is the only arithmetic move. On this picture, u is S, v is A, and w of u v is the four on their edge. A route through u costs d of u plus that edge weight. If that new cost is smaller than d of v, then replace d of v with it. The test comes first. The assignment happens only when the test wins. For A, the source contributes zero and the edge contributes four. Together they make four, so A receives four. For B, the source contributes zero and the edge contributes two. Together they make two, so B receives two. Now compare the unsettled rim. A carries four. B carries two. The smallest tentative distance belongs to B, so B is the greedy choice. Relax B to A. B contributes two and the edge contributes one. Together they make three, better than four, so A changes to three. A's predecessor changes from S to B at the same decision. The route record now agrees with the lower value. Next, B contributes two and the edge to C contributes eight. Together they make ten, so C receives ten. For D, B contributes two and the edge contributes ten. Together they make twelve, so D receives twelve. The live rim now reads A at three, C at ten, and D at twelve. Those are the finite candidates touching the blue region. The smallest is A at three. Settle A, grow the blue region, and update the crossing edges around the same weighted graph. Relax A to C. A contributes three and the edge contributes five. Together they make eight, so C falls from ten to eight. Now C has eight, D has twelve, and E is unreached. The smallest is C. Settle C and let the blue region reach it. Relax C to D. C contributes eight and the edge contributes two. Together they make ten, so D drops from twelve to ten immediately. Relax C to E. C contributes eight and the edge contributes six. Together they make fourteen, so E receives fourteen. The rim has D at ten and E at fourteen. Ten is smaller, so D is next. The region grows through D and the yellow boundary moves outward. Relax D to E. D contributes ten and the edge contributes three. Together they make thirteen, so E falls from fourteen to thirteen. Only E remains, carrying thirteen. Settle it. The blue region now covers every node, and no crossing edge remains. Read the final distances directly from the node labels: S zero, B two, A three, C eight, D ten, and E thirteen. The predecessor tree gives the route to E backwards: E to D, D to C, C to A, A to B, and B to S. Reverse that walk and its total is thirteen. The arithmetic explains every update, and the growing region shows every greedy commitment. What remains is to prove why the smallest label on the frontier is safe to make permanent.

Freeze one generic greedy step. The blue polygon is the settled region. Its yellow crossing edges are the frontier, and C carries the smallest tentative distance there: eight. Suppose a cheaper route P to C exists. It begins at S inside the polygon and ends at C outside, so it must cross the frontier for the first time. Call the first unsettled node on that route x. The only part of P we need is the short local prefix from u to x, ending exactly at x. Every edge leaving a settled node was relaxed when that node settled. Therefore the cost already spent along the prefix P sub x cannot be less than the tentative distance written at x. The greedy choice points to C because eight is the smallest frontier label. Since x is also on that frontier, d of x is at least d of C, which is eight. So the proposed cheaper route has already spent at least eight when it reaches x. It still has the remaining segment from x to C ahead of it. Every remaining edge has non-negative weight. Continuing from x cannot reduce the amount already spent, so P cannot reach C for less than eight. That contradiction makes eight final. The same frontier-crossing argument applies at every greedy step, which is why settled labels never need to reopen. Now change only one fact. This three-node graph has S to X of weight one, S to Y of weight four, and a red edge from Y to X of weight minus four. Relaxing S gives X one and Y four. The greedy rule points at X because one is smaller, so it settles X and grows the region there. But the other route walks S to Y and then Y to X. Its two weights are four and minus four. Together they total zero. Zero is smaller than one. The negative edge discounts the route after X was declared final, so the non-negative step in the proof has failed. Dijkstra's algorithm therefore requires non-negative weights. When a graph really contains negative edges, Bellman-Ford is the algorithm to reach for instead.

The whole algorithm fits into four numbered steps. The graph is in the state just after B settles: the blue region contains S and B, and its yellow crossing edges form the current frontier. First, initialize the labels; the source gets zero. Second, choose the smallest unsettled label; here A at three is next. Third, relax its outgoing edges. Fourth, repeat while the frontier still has a node. A plain array finds the minimum by scanning every key: three, ten, twelve, infinity. One scan costs V, and V choices give V times V, which is order V squared. A priority queue stores exactly the unsettled rim. Its smallest key is A's three. Pop A, settle it, and let the filled region grow through A. Relaxing A improves C. Decrease C's queue key from ten to eight, and the node label beside C changes to eight with the queue key. Those are the two heap operations Dijkstra needs: pop-min chooses the next settled node, and decrease-key records a better route without scanning the whole graph. Every node is popped once, giving V pop-min operations. Every edge can trigger a decrease-key, giving at most E lowerings. A binary heap makes each operation cost log V. The total is order V plus E, multiplied by log V. Finish the same run. C settles at eight. Its relaxation lowers D to ten. D then settles, which makes E reachable at fourteen. Relaxing D lowers E to thirteen, and E settles last. The blue region grows at each commitment. Each improvement also records a predecessor. The surviving choices form the shortest-path tree: S to B, B to A, A to C, C to D, and D to E. The final state carries the whole algorithm: a filled settled region, the tree that recovers every route, and no frontier edge left to cross. Non-negative weights are what make each greedy step permanent.