0:18

And initially, our x is going to be just the source for text itself.

Â So, now we enter the main while loop and so, remember in the while loop,

Â we say well, let's scan all of the edges whose tail is in the vertices we've

Â already looked at, whose tail is in x and whose head is outside of x.

Â Now, in this first iteration, there are two such edges,

Â there's the edge (s,v) and the edge (s,w).

Â So how do we know which of these two to choose?

Â Well, we evaluate Dijkstra's Greedy criterion.

Â And so remember what that is, Dijkstra's Greedy score for

Â a given edge (v,w) that's crossing the frontier is just the previously computed

Â shortest path distance for the tail of the arc plus the length of the arc itself.

Â So at this point, (s,v) has a greedy score of 0 + 1,

Â which is 1, and the arc (s,w) has a greedy score of 0 + 4, which is 4.

Â So obviously (s,v) is going to be the shorter of those two.

Â So we use the edge (s,v), this is playing the role of v*w* on the previous slide.

Â And the algorithm then suggests that we should add v to our set x.

Â So we suck in v, and our new x consists of s,

Â n, v, and it also tells us how to compute the shortest path distance and

Â the shortest path from s to v.

Â Namely, in the A array, we just write down what

Â was the Dijkstra's greedy score for this particular edge, and that was 0 + 1, or 1.

Â It also tells how to compute the shortest path for v.

Â Namely, we just inherit the shortest path to the tail of the arc,

Â which in this case, is the empty path from s to itself and then we tack on the end,

Â we append the arc we used to get here, the arc S(v).

Â So now we go to the next iteration of the while loop,

Â so with our new set capital X consisting of s and v.

Â And now again, we want to look at all edges which are crossing the frontier,

Â edges that have tail in x and head outside x.

Â And now we see there's three such crossing edges.

Â There's (s,w), there's (v,w), and there's (v,t).

Â All of those have the tail in x and the head outside of x.

Â So we need to compute Dijksta's greedy score for each of those three and

Â then pick the minimum.

Â So let's go from bottom to top.

Â So first of all, we can look at the arc (s,w).

Â And the greedy score here is the shortest path distance for the tail, so

Â it's 0 plus the length of the arc, which is 4.

Â So here we get a 4 in this iteration.

Â Then if we do this cross-bar edge, this (v,w) edge, the Dijkstra's greedy

Â score is the A value, or the shortest path distance value of the tail.

Â And we computed that last iteration, that A(V) value is 1,

Â we add to that the length of the arc, which in this case is 2.

Â So this edge (v,w) has a score of 3.

Â 3:11

Finally there's the arc (v,t) and here we're going to add 1, which is

Â the shortest path distance of the tail of the arc plus the edge length, which is 6.

Â So that has the worst score.

Â So, since the edge (v,w) has the smallest score, that's the one that guides how we

Â supplement x and how we compute the shortest path distances and

Â the shortest path for the newly acquired vertex w.

Â So the changes are, first of all, we enlarge x.

Â So x is now everything, but t.

Â 3:42

And then how do we compute things for w?

Â Well, the shortest path, so the r entry in the A array is just going to be

Â Dijkstra's greedy score in the previous iteration.

Â So that was 1+2, so it's going to be equal to 3.

Â And then what is the shortest path?

Â How do we fill up the array B?

Â Well we inherit the shortest path to the tail of the arc, which in this case,

Â is the arc (s,v) and then we append the arc that we used to choose

Â this new vertex w, so that's the arc (v,w).

Â So the new path is just the (s,v,w) path, okay, so

Â it's what we compute is the shortest path from s to w in this graph.

Â So now we proceed to the final iteration of Dijkstra's algorithm.

Â We know what vertex we're going to bring in to x, it's going to be the vertex t,

Â that's the only one left.

Â But we still have to compute by which edge we discovered t and

Â bring it in to the set x.

Â So we have to compute the greedy score for each of the two crossing arcs, (v,t) and

Â (w,t).

Â And then this final iteration, the score for the arc (v,t) is unchanged.

Â So this is still going to be the a value of its tail 1,

Â plus the length of the arc, 6.

Â So the score here is still 7, and now for the first time,

Â (w,t) is a crossing edge of the frontier.

Â And when we compute its score, it's the a value of its tail w, which is 3,

Â plus the length of this arc which is 3, so I get a greedy score of 6.

Â So by Dijkstra's greedy criterion, we picked the edge (w,t) instead of

Â the edge (v,t), and of course, that doesn't matter who gets brought into X,

Â but it does matter how we compute the A and B values for T.

Â 5:19

So in the final iteration, we compute (a,t) to be the Dijkstra's greedy

Â score of the edge that we picked, which is the edge (w,t), and the score was 6.

Â So we compute the shortest path distance from s to t to be 6.

Â And then what is the path itself?

Â Well, we inherit the shortest path to the tail of the arc that we used to

Â discover t, so that's the shortest path to w,

Â which we previously computed as being the path through v.

Â And then we append the edge we used to discover t, so we append the edge (w,t).

Â So the shortest path from s to t, we're going to compute

Â as the zigzag path, s goes to v goes to w goes to t.

Â 6:01

And then now, dx is all the vertices, we've computed it for

Â everything, this is our final output.

Â The contents of the, especially the A array is the final output,

Â shortest path distances from s to all of the four possible destinations.

Â And if you go back and compare this to the example you went through the quiz,

Â you will see at least on this example,

Â indeed Dijkstra's algorithm corrects the shortest path distances.

Â Now I've said it before, I'm going to say it again.

Â Someone shows you their algorithm works just on some examples,

Â especially a pretty simple four note example,

Â you should not jump to the conclusion that this algorithm always works.

Â Sometimes algorithms work fine on small examples, but

Â break down once you go to more interesting complicated examples.

Â So I definitely owe you a proof.

Â The Dijkstra's algorithm works not only in this network, but in any network.

Â And actually it doesn't work in any network,

Â it's only going to work in any network with non-negative edge lengths.

Â So to help you appreciate that, let's conclude this video with a non example,

Â showing what goes wrong in Dijkstra's algorithm

Â when you have networks with negative edge lengths.

Â 7:02

So before I actually give you a real non-example,

Â let me just answer a preliminary question, which you might have, and

Â this would be a very good question if it's something that has occurred to you.

Â The question would be well, why are these negative edge links such a big deal?

Â Why can't we just reduce shortest path computation with negative edge links

Â to the problem of computing shortest paths with non-negative edge links, right?

Â So why don't we just sort of clear things out?

Â We just add a big number to all the edges, that makes them all non-negative and

Â then we just run Dijkstra's algorithm and we're good to go.

Â 7:31

So this is exactly the sort of question you should be looking to ask if

Â as a computer scientist, as a serious programmer.

Â When confronted with a problem, you always want to look for

Â ways to reduce it to simpler problems that you already know how to solve.

Â And this is a very natural idea of how to reduce a seemingly harder shortest path

Â problem to one we already know how to solve using Dijkstra's algorithm.

Â The only problem is, it doesn't quite work.

Â Why doesn't it work?

Â Well, let's say you have a graph, and the most negative edge is minus ten.

Â So, all the other edge links are minus 10 and above.

Â So then, what you want to do is add 10 to every single edge in the network, and

Â that ensures that all the lengths are non-negative.

Â Run Dijkstra's algorithm, get your shortest path.

Â The issue is that different paths between a common origin and

Â destination have differing numbers of edges.

Â So, some might have five edges, some might have two edges.

Â Now, if you add 10 to every single edge in the graph,

Â you're going to change path lengths by different amounts.

Â If a path has five edges, it's going to go up by 50 when you add 10 to every edge.

Â If a path has only two edges,

Â it's only going to go up by 20 when you add 10 to every edge.

Â So as soon as you start changing the path lengths of different paths by different

Â amounts, you might actually screw up which path is the shortest.

Â The path which is shortest of the new edge lengths

Â need not be the one the shortest under the old edge lengths.

Â So that's why this reduction doesn't work.

Â 8:51

To be concrete, let's look at this very simple three vertex graph where

Â vertices s, v, and t and edge lengths as shown 1, -5 and -2.

Â Now what I hope is clear is that in this graph, the shortest path,

Â the one with the minimum length, is the too hot path, s, v, t.

Â That has length minus 4.

Â The direct s,t arc has length minus 2, which is bigger than minus 4.

Â So the upper path is the shortest path.

Â Now suppose we try to massage this by adding a constant to every edge so

Â that all edge links were non-negative.

Â We have to add 5 to every edge, because that's the biggest negative number,

Â the (v,t) edge.

Â So that would give us new edge lengths of 6, and 0, and 3.

Â And now the problem is, we have changed which path is the shortest one.

Â We added 10 to the top half and

Â only 5 to the bottom half and as a result, they've reversed.

Â So now the bottom path (s,t) is actually the shorter one, so

Â if you run Dijkstra's on this graph, it's going to come back with a path (s,t),

Â even though that's not in fact the shortest path in the original network,

Â the one that we actually care about, okay.

Â So that's why you can't just naively reduce shortest paths with negative edge

Â lengths to shortest paths with non-negative edge lengths.

Â Moreover, on this very same super simple three nug graph,

Â we can try running Dijkstra's shortest path algorithm.

Â It's perfectly well defined, it'll produce some output,

Â but it's actually going to be wrong.

Â It is not going to compute shortest path distances correctly in this graph, so

Â let me show you why.

Â Of course, the initialization will work as it always does, so it's going to start by

Â saying the shortest path distance from s to itself is 0 by the empty path.

Â 10:30

And then, what's it going to do next?

Â It's going to say, okay, well, we need to enlarge the set capital, x, by one vertex,

Â and there are two crossing edges as the (x,v) edge and the (s,t) edge.

Â And what's it going to do?

Â It's going to use the Dijkstra's greedy score.

Â So, the score of this upper edge is going to be 1,

Â and the score of this bottom edge is going to be minus 2.

Â because remember, you take the previously computed shortest path value of the tail,

Â that is 0 in both cases, and then you add the edge length.

Â So the edge lengths are 1 and minus 2, so the scores are 1 and minus 2.

Â Which of these is smaller?

Â Well evidently, the (s,t) arc has the smaller score, minus 2.

Â So what is Dijkstra's algorithm going to do?

Â It's going to say, yes, let's go for this edge, (s,t).

Â Let's bring T into the set capital X.

Â T is now part of the conquered territory.

Â 11:19

And of course, as soon as you bring a node into the set X, into conquered territory,

Â you have to commit or Dijkstra's algorithm chooses

Â to commit to its shortest path distance and its shortest path.

Â What is the definition of its shortest path distance, as computed by Dijkstra?

Â Well it's just a greedy score.

Â So it's going to assign the vertex t, the shortest path distance of minus 2,

Â and the path is going to be just the arc, (s,t).

Â But notice that this is in fact wrong.

Â The shortest path distance from s to t is not minus 2 in this graph.

Â There's another path, namely the one that goes through v,

Â that has length minus 4, less than minus 2.

Â So Dijkstra computes incorrect shortest path distances

Â on this trivial three note graph.

Â So to summarize the story so far, we've described Dijkstra's algorithm.

Â I've showed you that it works in a very simple example that doesn't have

Â negative edge lengths.

Â And I've showed you that it doesn't work in an even simpler example that

Â does have negative edge lengths.

Â So I've both given you some plausibility that it might work generally, at least for

Â non negative edge lengths, but I've also tried to sow some seeds of doubt.

Â That it's not at all clear at this point if Dijkstra's algorithm is always

Â correct or not, even if you have non negative edge lengths.

Â And certainly,

Â if it is always correct, there better be a foolproof argument for why.

Â You should be demanding an explanation of a claim

Â that Dijkstra is correct in any kind of generality.

Â That's the subject of the next video.

Â