The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).
Dijkstra's Algorithm: Examples
Loading...
來自 Stanford University 的課程
Graph Search, Shortest Paths, and Data Structures
883 個評分
從本節課中
Week 2
Dijkstra's shortest-path algorithm.
與講師見面
Tim RoughgardenProfessor
Computer Science
So let's just see how it works in the same example we traced through earlier.
So we start out just by initializing things in the obvious way, so
the shortest path distance from s to itself we say is 0.
And the shortest path from s to itself is just the empty path.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
