WEBVTT 00:00:00.058 --> 00:00:03.342 Dijkstra's algorithm finds the cheapest route from one source 00:00:03.425 --> 00:00:05.504 to every node in a graph. 00:00:06.304 --> 00:00:09.460 The picture to keep is a filled region that spreads outward, 00:00:09.543 --> 00:00:13.271 with the edges crossing its boundary forming a live frontier. 00:00:14.923 --> 00:00:16.734 Here are six nodes. 00:00:16.931 --> 00:00:22.052 S is the source, and A, B, C, D and E are the other places. 00:00:22.608 --> 00:00:26.391 The gray connections are weighted edges. Their numbers measure cost, 00:00:26.474 --> 00:00:30.376 so a path is cheap when the sum of its edge weights is small. 00:00:31.057 --> 00:00:34.270 The weights are four, two, one, five, 00:00:34.353 --> 00:00:38.615 eight, ten, two again, six, and three. 00:00:38.812 --> 00:00:40.400 Every one is non-negative. 00:00:40.483 --> 00:00:42.678 That condition will carry the proof. 00:00:43.475 --> 00:00:47.038 This blue patch around S is the settled region we will grow. 00:00:47.121 --> 00:00:50.186 The two yellow edges leaving it are the frontier. 00:00:50.290 --> 00:00:51.544 Keep that boundary alive 00:00:51.544 --> 00:00:55.968 in your eye while the numbers decide which node the patch reaches next. 00:00:56.764 --> 00:00:59.923 First see why counting edges is not enough. 00:01:00.120 --> 00:01:03.879 Start at S, then B, then D, then E. 00:01:03.962 --> 00:01:06.367 This route uses only three edges. 00:01:07.163 --> 00:01:10.494 The three-hop route pays two, ten, and three. 00:01:10.577 --> 00:01:13.491 Together those weights total fifteen. 00:01:14.706 --> 00:01:18.443 The other route goes S, B, A, C, D, E. 00:01:18.526 --> 00:01:22.532 Its five weights are two, one, five, two, and three. 00:01:22.636 --> 00:01:24.854 Together they total thirteen. 00:01:25.650 --> 00:01:27.927 Fifteen is greater than thirteen. 00:01:28.124 --> 00:01:29.840 More hops can cost less, 00:01:29.923 --> 00:01:34.278 so every decision must use the accumulated weights rather than the hop count. 00:01:35.074 --> 00:01:40.033 Each node carries a tentative distance: the cheapest route found so far. 00:01:40.136 --> 00:01:42.758 Unreached nodes have no number yet. 00:01:42.841 --> 00:01:44.746 The source is different. 00:01:45.059 --> 00:01:49.959 Reaching S from S costs zero, so zero is final from the start. 00:01:50.930 --> 00:01:53.705 Relaxation is the only arithmetic move. 00:01:53.855 --> 00:02:00.033 On this picture, u is S, v is A, and w of u v is the four on their edge. 00:02:00.171 --> 00:02:03.713 A route through u costs d of u plus that edge weight. 00:02:04.464 --> 00:02:09.909 If that new cost is smaller than d of v, then replace d of v with it. 00:02:10.106 --> 00:02:11.988 The test comes first. 00:02:12.440 --> 00:02:15.505 The assignment happens only when the test wins. 00:02:16.418 --> 00:02:20.656 For A, the source contributes zero and the edge contributes four. 00:02:21.109 --> 00:02:24.395 Together they make four, so A receives four. 00:02:25.145 --> 00:02:29.105 For B, the source contributes zero and the edge contributes two. 00:02:29.255 --> 00:02:32.379 Together they make two, so B receives two. 00:02:33.245 --> 00:02:35.624 Now compare the unsettled rim. 00:02:35.707 --> 00:02:37.275 A carries four. 00:02:37.425 --> 00:02:38.993 B carries two. 00:02:39.248 --> 00:02:43.776 The smallest tentative distance belongs to B, so B is the greedy choice. 00:02:44.573 --> 00:02:46.535 Relax B to A. 00:02:46.639 --> 00:02:50.062 B contributes two and the edge contributes one. 00:02:50.145 --> 00:02:54.813 Together they make three, better than four, so A changes to three. 00:02:55.610 --> 00:02:59.802 A's predecessor changes from S to B at the same decision. 00:02:59.998 --> 00:03:03.087 The route record now agrees with the lower value. 00:03:03.942 --> 00:03:08.027 Next, B contributes two and the edge to C contributes eight. 00:03:08.110 --> 00:03:11.245 Together they make ten, so C receives ten. 00:03:12.216 --> 00:03:16.315 For D, B contributes two and the edge contributes ten. 00:03:16.849 --> 00:03:20.519 Together they make twelve, so D receives twelve. 00:03:21.733 --> 00:03:27.075 The live rim now reads A at three, C at ten, and D at twelve. 00:03:27.178 --> 00:03:30.476 Those are the finite candidates touching the blue region. 00:03:30.959 --> 00:03:33.419 The smallest is A at three. 00:03:33.502 --> 00:03:35.706 Settle A, grow the blue region, 00:03:35.789 --> 00:03:39.459 and update the crossing edges around the same weighted graph. 00:03:40.256 --> 00:03:45.620 Relax A to C. A contributes three and the edge contributes five. 00:03:45.724 --> 00:03:49.672 Together they make eight, so C falls from ten to eight. 00:03:50.469 --> 00:03:54.893 Now C has eight, D has twelve, and E is unreached. 00:03:55.090 --> 00:03:59.792 The smallest is C. Settle C and let the blue region reach it. 00:04:00.798 --> 00:04:05.907 Relax C to D. C contributes eight and the edge contributes two. 00:04:06.069 --> 00:04:10.760 Together they make ten, so D drops from twelve to ten immediately. 00:04:11.522 --> 00:04:16.829 Relax C to E. C contributes eight and the edge contributes six. 00:04:17.002 --> 00:04:20.625 Together they make fourteen, so E receives fourteen. 00:04:21.515 --> 00:04:25.231 The rim has D at ten and E at fourteen. 00:04:25.404 --> 00:04:28.052 Ten is smaller, so D is next. 00:04:28.225 --> 00:04:32.186 The region grows through D and the yellow boundary moves outward. 00:04:33.214 --> 00:04:38.474 Relax D to E. D contributes ten and the edge contributes three. 00:04:38.787 --> 00:04:43.629 Together they make thirteen, so E falls from fourteen to thirteen. 00:04:44.112 --> 00:04:46.969 Only E remains, carrying thirteen. 00:04:47.166 --> 00:04:48.258 Settle it. 00:04:48.455 --> 00:04:52.914 The blue region now covers every node, and no crossing edge remains. 00:04:53.710 --> 00:04:56.753 Read the final distances directly from the node labels: 00:04:56.880 --> 00:05:02.732 S zero, B two, A three, C eight, D ten, and E thirteen. 00:05:03.552 --> 00:05:06.490 The predecessor tree gives the route to E backwards: 00:05:06.617 --> 00:05:11.332 E to D, D to C, C to A, A to B, and B to S. 00:05:11.563 --> 00:05:14.513 Reverse that walk and its total is thirteen. 00:05:15.565 --> 00:05:17.885 The arithmetic explains every update, 00:05:17.968 --> 00:05:20.987 and the growing region shows every greedy commitment. 00:05:21.091 --> 00:05:25.038 What remains is to prove why the smallest label on the frontier is safe 00:05:25.038 --> 00:05:26.351 to make permanent. 00:05:26.464 --> 00:05:28.984 Freeze one generic greedy step. 00:05:29.088 --> 00:05:31.875 The blue polygon is the settled region. 00:05:31.979 --> 00:05:34.543 Its yellow crossing edges are the frontier, 00:05:34.626 --> 00:05:37.773 and C carries the smallest tentative distance there: 00:05:37.970 --> 00:05:38.876 eight. 00:05:39.789 --> 00:05:42.831 Suppose a cheaper route P to C exists. 00:05:43.028 --> 00:05:45.849 It begins at S inside the polygon and ends 00:05:45.849 --> 00:05:50.366 at C outside, so it must cross the frontier for the first time. 00:05:51.418 --> 00:05:54.493 Call the first unsettled node on that route x. 00:05:54.576 --> 00:05:59.160 The only part of P we need is the short local prefix from u to x, 00:05:59.243 --> 00:06:01.566 ending exactly at x. 00:06:02.177 --> 00:06:06.404 Every edge leaving a settled node was relaxed when that node settled. 00:06:06.507 --> 00:06:08.226 Therefore the cost already spent 00:06:08.226 --> 00:06:13.938 along the prefix P sub x cannot be less than the tentative distance written at x. 00:06:14.735 --> 00:06:19.264 The greedy choice points to C because eight is the smallest frontier label. 00:06:19.460 --> 00:06:25.626 Since x is also on that frontier, d of x is at least d of C, which is eight. 00:06:26.423 --> 00:06:31.149 So the proposed cheaper route has already spent at least eight when it reaches x. 00:06:31.345 --> 00:06:34.968 It still has the remaining segment from x to C ahead of it. 00:06:35.881 --> 00:06:38.877 Every remaining edge has non-negative weight. 00:06:39.074 --> 00:06:42.497 Continuing from x cannot reduce the amount already spent, 00:06:42.580 --> 00:06:45.495 so P cannot reach C for less than eight. 00:06:46.291 --> 00:06:50.842 That contradiction makes eight final. The same frontier-crossing argument applies 00:06:50.842 --> 00:06:55.429 at every greedy step, which is why settled labels never need to reopen. 00:06:56.225 --> 00:06:58.313 Now change only one fact. 00:06:58.396 --> 00:07:04.132 This three-node graph has S to X of weight one, S to Y of weight four, and a red edge 00:07:04.132 --> 00:07:06.850 from Y to X of weight minus four. 00:07:07.646 --> 00:07:10.979 Relaxing S gives X one and Y four. 00:07:11.176 --> 00:07:12.244 The greedy rule points 00:07:12.244 --> 00:07:16.842 at X because one is smaller, so it settles X and grows the region there. 00:07:17.639 --> 00:07:20.841 But the other route walks S to Y and then Y to X. 00:07:20.924 --> 00:07:23.778 Its two weights are four and minus four. 00:07:23.861 --> 00:07:26.126 Together they total zero. 00:07:26.923 --> 00:07:29.176 Zero is smaller than one. 00:07:29.372 --> 00:07:33.086 The negative edge discounts the route after X was declared final, 00:07:33.169 --> 00:07:36.327 so the non-negative step in the proof has failed. 00:07:37.124 --> 00:07:41.131 Dijkstra's algorithm therefore requires non-negative weights. 00:07:41.327 --> 00:07:45.693 When a graph really contains negative edges, Bellman-Ford is the algorithm 00:07:45.693 --> 00:07:47.284 to reach for instead. 00:07:47.375 --> 00:07:50.696 The whole algorithm fits into four numbered steps. 00:07:50.800 --> 00:07:55.871 The graph is in the state just after B settles: the blue region contains S and B, 00:07:55.954 --> 00:07:59.252 and its yellow crossing edges form the current frontier. 00:08:00.049 --> 00:08:04.160 First, initialize the labels; the source gets zero. 00:08:04.357 --> 00:08:07.492 Second, choose the smallest unsettled label; 00:08:07.584 --> 00:08:09.721 here A at three is next. 00:08:09.906 --> 00:08:12.717 Third, relax its outgoing edges. 00:08:12.809 --> 00:08:16.327 Fourth, repeat while the frontier still has a node. 00:08:17.019 --> 00:08:20.619 A plain array finds the minimum by scanning every key: 00:08:20.711 --> 00:08:22.999 three, ten, twelve, infinity. 00:08:23.172 --> 00:08:28.781 One scan costs V, and V choices give V times V, which is order V squared. 00:08:29.566 --> 00:08:32.899 A priority queue stores exactly the unsettled rim. 00:08:33.002 --> 00:08:35.430 Its smallest key is A's three. 00:08:35.626 --> 00:08:40.109 Pop A, settle it, and let the filled region grow through A. 00:08:40.905 --> 00:08:43.191 Relaxing A improves C. 00:08:43.274 --> 00:08:45.768 Decrease C's queue key from ten to eight, 00:08:45.851 --> 00:08:49.660 and the node label beside C changes to eight with the queue key. 00:08:50.456 --> 00:08:55.182 Those are the two heap operations Dijkstra needs: pop-min chooses the next settled 00:08:55.182 --> 00:08:59.710 node, and decrease-key records a better route without scanning the whole graph. 00:09:00.507 --> 00:09:04.095 Every node is popped once, giving V pop-min operations. 00:09:04.292 --> 00:09:08.727 Every edge can trigger a decrease-key, giving at most E lowerings. 00:09:09.431 --> 00:09:12.913 A binary heap makes each operation cost log V. 00:09:12.996 --> 00:09:17.014 The total is order V plus E, multiplied by log V. 00:09:17.706 --> 00:09:19.274 Finish the same run. 00:09:19.470 --> 00:09:21.271 C settles at eight. 00:09:21.374 --> 00:09:23.906 Its relaxation lowers D to ten. 00:09:24.091 --> 00:09:27.993 D then settles, which makes E reachable at fourteen. 00:09:28.178 --> 00:09:32.474 Relaxing D lowers E to thirteen, and E settles last. 00:09:32.671 --> 00:09:35.214 The blue region grows at each commitment. 00:09:36.010 --> 00:09:38.728 Each improvement also records a predecessor. 00:09:38.925 --> 00:09:41.956 The surviving choices form the shortest-path tree: 00:09:42.059 --> 00:09:48.016 S to B, B to A, A to C, C to D, and D to E. 00:09:48.929 --> 00:09:53.316 The final state carries the whole algorithm: a filled settled region, 00:09:53.399 --> 00:09:57.951 the tree that recovers every route, and no frontier edge left to cross. 00:09:58.147 --> 00:10:01.886 Non-negative weights are what make each greedy step permanent.