Tip:
Highlight text to annotate it
X
So let's just see how it works on the same example we traced here earlier. So we
sorta have just by initializing things in the obvious way. So, the shortest path
distance from S to itself is zero. And the shortest path from S to itself is just the
empty path. And initially X is going to be just the source vertex itself. So now we
enter them in 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 SV, and the edge SW. So how do we know which of
these two to use. Well we evaluate Dijkstra's greedy criterion. You guys
remember what that is. Dijkstra's greedy score for a given edge VW That's crossing
the frontier, is just the previously computed shortest path distance for the A
tail of the arc plus the length of the arc itself. So at this point SV has a greedy
score of zero plus one, which is one, and the arc S comma W has a greedy score of
zero plus four, which is four. So obviously SV is going to be the shorter of
those two, so we use the edge SV, this is playing the role of V star W star on the
previous slide, and the algorithm them suggests we should add V to our set X, so
we suck in V, and our new X consists of S and V. [sound]. 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 greedy, the Dijkstra's greedy score
for this particular edge, and that was zero plus one, or one. It also tells us
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, was 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 to V.
So now we go to the next iteration of the while loop. So with our new set
[inaudible] consisting of S and v. Now again we wanna look at all edges which are
crossing the fr ontier. Edges that have tail in X and head outside x. And know we
see there is three such crossing edges. There is SW there is VW and there is VT
all of those have the tail in X and the head outside of X, so we need to compute
Dijkstra'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 SVSW, excuse me. And
the greedy score here is the shortest path distance for the tail, so it's zero, plus
the length of the arc, which is four. So here we get a four in this iteration.
Then, if we do this crossbar edge, this VW edge, the Dijkstra greedy score is the a
value, or the shortest path distance value of the tail, and we computed that last
iteration. The a of V value is one. We add to that the length of the arc, which in
this case is two. So this edge three, [inaudible] this edge VW has a score of
three. Finally there's the arc VT, and here, we're gonna add one, which is the
shortest path distance of the tail of the arc, plus the edge length which is six. So
that has the worst score. So since the edge VW has the smallest score, that's the
one that guides how we supplement X, and how we compute the shortest path distances
in 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. And then how do we
compute things for W? Well the shortest path, so our entry in A array is just
going to be Dijkstra's [inaudible] greedy score in the previous set of rations so
that was one plus two so that's going to be equal to three. 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 SV and then we append the arc that
we used to choose this new vertex W so that's the arc VW. So the new path is just
the SVW Path, okay? So [inaudible] we computed 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 into X. It's gonna be the vertex T. That's the
only one left. But we still have to compute by which edge we discover T and
bring it into the set X. So we have to compute the [inaudible] score for each of
the two crossing arcs... VT and WT. And in this final iteration the score for the arc
(V, T) is unchanged. So this is still gonna be the a value of its tail, one,
plus the length of the arc, six. So the score here is still seven. And now, for
the first time, WT is a crossing edge of the frontier, and when we compute its
score, it's the a value of its tail W, which is three, plus the length of this
arc, which is three, so we get a rescore of six. So by Dijkstra's greedy criterion,
we pick the edge wt instead of the edge VT, 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.
So in the final iration. We compute AT to be the Dijkstra greedy score of the edge
that we picked, which is the edge, WT and the score was six. So we compute the
shortest path distance from S to T to be six. And then what is the path itself?
Well, we inherit the shortest path from the tail of the arc that we used to
discover T. So that's the shortest path to W, which we previously computes as being
the path through V. And then we append the edge we used to discover T, so we append
the edge, WT. So the shortest path from S to T, we're going to compute as the
zig-zag path. S. Goes to V, goes to T, Sorry, Goes to W, goes to T. And then now
indeed X is all the vertices. We've computed it for everything. This is our
final output. The contents of the, especially the A array, this, 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 to the quiz, you
will see at least on this example, indeed. Dijkstra's algorithm corrects pa, the
shortest path distances. Now, I've said it before and I'll say it again. If someone
shows you their algorithm works just on some example, especia lly a pretty simple
four note example, you should not jump to the conclusion that this algorithm always
works. Sometimes the algorithms work fine on small examples, but break down once you
go to more interesting complicated examples. So I definitely owe you a proof
that 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 gonna work in any network with
non-negative edge lengths. So to help you appreciate that, Let's conclude this video
with a nonexample showing what goes wrong in Dijkstra's algorithm when you have
networks with negative edge lengths. So before I actually give you a, a real non
example let me just answer preliminary question which you might have and should
be have very good question if it something that's occurred to you. The question would
be well, ya why is it, why are these negative instance such a big deal. Why
can't we just reduce shortest path competition with negative edge links to
the problem of computing shortest paths with non negative edge links. Right so
whatever just clear things out we just add big number to all the edges that makes
them all non-negative and now we just run Dijkstra's algorithm and we're good to go.
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 sort of path problem to one we already know how to solve using dutch
[inaudible] algorithm. The only problem is it doesn't quite work. One isn't gonna
work. Well if you, Let's say you have a graph, and the most negative edge is -ten.
So all the edge lengths are negative ten and above. So then what you'd want to do
is add ten to every single edge in the network, and that insures that all of the
edge lengths are non negative, run Dijkstra's algorithm, get your shortest
path. The is sue 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 ten 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 ten to every edge. If a path has only two edges, It's only going
to go up by twenty, when you add ten 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 under
the new edge lengths need not be the one that's shortest under the old edge
lengths. So that's why this reduction doesn't work. To be concrete, let's look
at this very simple three vertex graph with vertices s, v, and t and edge lengths
as shown. One minus five and minus two. Now what I hope is clear, is that in this
graph. The shortest path. The one with the minimum length is the two hot path Svt,
That has length minus four. The direct STR has length minus two which is bigger than
minus four. So the upper path is the shortest path. Now, suppose we tried to
massage this by adding a constant to every edge so all edge lengths were
non-negative. We'd have to add five to every edge because that's the biggest
negative number the VT edge. So that would give us new edge lengths of six. And zero
ends three. [sound]. And now the problem is, we've changed which path is the
shortest one. We added ten to the top path and only five to the bottom path and as a
result, they've reversed. So now the bottom path ST is actually the shorter
one. So if you run Dijkstra on this graph, it's going to come with the path ST 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
path with negative edge lengths to shortest paths with non-negative edge
lengths. Moreover on this very same, super simple thre e node graph, You know, we can
try to run, running dikes for shortest path algorithm. It's perfectly well
defined. It will 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. Unless of course initialization will work as it always does. So it's gonna
start by saying the shortest path distance from S to itself is zero via the empty
path. And then, what's it going to do next? It's going to say well we need to
enlarge the set capital X by one vertex and there are two crossing edges, it's the
XV edge and the ST edge. And what's it going to do. It's going to use the
Dijkstra Greedy score. So the score of this upper edge is going to be one, and
the score of this bottom edge. Is going to be negative two. 'Cause remember, you take
the previously computed shortest path [inaudible] of the tail, that's zero in
both cases. And then you add the edge lengths. So the edge lengths are one and
minus two, so the scores are one and minus two. Which of these is smaller? Well
evidently, the ST arc has the smaller score minus two. So what is Dijkstra's
algorithm gonna do? It's going to say yes, let's go for this edge ST. Let's bring T
into the set capital X. T is now part of the conquered territory. And of course as
soon as you bring a node into the set X, into the [inaudible] territory, you have
to commit or Dijkstra's algorithm chooses to commit to a shortest path distance and
a shortest path. What is the definition of its shortest path distance, as computed by
Djikstra? Well it's just a degree score. So it's going to assign the vertex t the
shortest path distance of minus two, 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 two, in this graph. There is another path, namely the one that goes thorough V
that has length minus four, less than minus two. So, [inaudible] computes
incorrect shortest path distances on this trivial 3-note graph. So t o summarize the
story so far, We've described Dijkstra's algorithm. I've shown you that it works in
a very simple example that doesn't have negative edge lines and I've showed you
that it doesn't work in and even simpler example that does have negative edge
lines. So, I've both given you some plausibility that it might work generally
at least for non negative edges links. But I've also tried to sew some seeds of doubt
that it's not an all clear if at this point if Dijkstra's algorithm is always
clear correct or not even if you have non-negative edge lengths and certainly if
it is always correct there better be a fool proof argument to why. You should be
demanding and explanation of a claim If Dijkstra's is correct in any kind of
generality. That's the subject of the next video.