The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).
Johnson's Algorithm II
Loading...
来自 Stanford University 的课程
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
343 个评分
从本节课中
Week 1
The Bellman-Ford algorithm; all-pairs shortest paths.
与讲师见面
Tim RoughgardenProfessor
Computer Science
We're now well positioned to state Johnson's algorithm in its full
generality. The input as usual is a directed graph G.
Each edge has a edge length C sub E, it could be positive or negative.
The input graph G may or may not have a negative cost cycle.
As usual, when we talk about solving a shortest path problem we mean that if
there is no negative cost cycle, then we have no excuse. So we better correctly
compute all of the desired shortest paths.
In this case between all pairs of vertices.
If there is a negative cost cycle, we're off the hook.
We don't have to compute shortest paths, but we.
need to correctly report that the graph does indeed have a negative cost cycle.
Step one is the same hack that we used in the example.
We want to make sure that there's a vertex from which we can reach everybody
else. So let's just add a new one that by
construction has that properties. So we add one new vertex to little s, we
add N new edges. One from s to each of the original
vertices and each of those new N edges has length zero.
We're going to call this new, bigger graph g prime.
The second step, just like in the example, is to run a shortest path
computation using this new vertex S as the source.
Since the graph G in general has negative etch cost, we have to resort to the
Belmont Ford out rhythm to execute the shortest path computation.
Recall that the Bellman-Ford Algorithm will do one of two things.
Either it will correctly compute the shortest path distances that we're after,
from the source vertex S to everybody else, or it will correctly report.
That the graph it was fed, namely g prime, contains [SOUND] a negative cost
cycle. Now, if g prime contains a negative cost
cycle, that cycle has to be the original graph, g.
Our, the new vertex, s, that we added, has no incoming arcs at all, so it
certainly can't be on any cycle, [SOUND] so any negative cycle is the
responsibility of the original graph, G. [SOUND] Therefore if Bellman-Ford finds
us a negative cost cycle, we're free to just halt and correctly report that same
result. So from here on out, we can safely assume
that G and G prime have no negative cost cycle, and therefore that the
Bellman-Ford algorithm did indeed correctly compute shortest path distances
from S to everybody else. As in the example, we are going to use
these shortest path distances, [SOUND] all of which are finite by construction.
As our vertex weights, our P sub Vs. We then form the new edges lengths, the C
primes, in the usual way. C prime of an edge E going from U to V is
the original length CE plus the weight of the tail P sub U minus the weight of the
head P sub V. In the example, we saw that the new edge
length C prime are all non-negative. We will shortly prove that, that property
holds in general. If you define your vertex weights in
terms of shortest path distances from the new vertex S to everybody else in this
augmented graph G Prime it is always the case that your new edge lengths would be
non-negative. Assuming that for now, it makes sense to
use Dijkstar's algorithm N times, once for each choice vertex to compute all
pairs shortest paths in the graph G with the new edge length C prime.
In a particular iteration of this four loop.
Say, when we're using the vertex u as the source vertex.
We're going to be computing n of the shortest path distances that we care
about. From u to the various n possible
destinations. And let's call those shortest paths
computed by Dijkstra in this iteration d prime of u, v.
So perhaps you're thinking that at this point we're done.
Right? We transformed the edge links using
re-weighting to make them non-negative and as we know once things are not
negative end Dijjkstra and you're good to go.
But there's one final piece of bookkeeping that we have to keep track
of. So, the shortest path distances that we
compute in step four, these D primes, these are the shortest path distances
with respect to the modified costs, the C primes.
And what we're responsible for outputting the shortest path distances with respect
to the original links, the C's. But fortunately there's a very easy way
to extract the true shortest path distances from.
The D primes from the shortest path distances relative to the modified costs.
We know that D primes are wrong, there computed with respect to the wrong costs.
But we know exactly what they're off by. So D primes are off by exactly P sub U
minus P sub V amount. So to go from the D primes back to
shortest path distances that we really care about, we just need to subtract that
term back off, and that's step five. [SOUND] That completes the description of
Johnson's Algorithm which, in effect, is a reduction from the all pairs shortest
path problem with general edge lengths to N plus one instances of the single source
version of the problem, only one of which has general edge lengths, N of which have
only non-negative edge lengths. [SOUND] Analyzing the running time of
Johnson's algorithm is straight forward. Let's just look at the work done in each
of the five steps. In step one, we just add one new vertex
and n new edges, so that takes o of n time to accomplish.
In step two we run the Bellman-Ford algorithm, so we know that takes O of M
times N time. In step three, we have to compute the
modified costs, but given the shortest path distances computed by Bellman Ford,
that's constant time per edge or O of N time overall.
In step four we went Dijkstra's out rhythm N times.
And, the running time of one indication is N X login.
In step five we do constant work for each choice of U and V, so O of N squared work
overall. So you can see that step four dominates
and the running time is equivalent to N invocations of Dijkstra's algorithm M
times N times log N. As usual when discussing graph algorithms
I am thinking about the graph as a least being weakly connected.
I'm thinking of the number of edges M as being big omega of N.
So why is this running time so cool? Well two reasons.
The first reason is that for sparse graphs this solution blows away the
previous algorithms that we had that could handle negative edge lengths.
The two previous solutions that we knew, that you could use with graphs with
negative edge lengths were either run Bellam Ford N times or used the
Floyd-Warshall. And in sparse graphs where M is big O of
N, both of those solutions run in cubic time or in cubed time.
This solution for sparse graphs, when M is O of N is of, of N squared Times a log
N factor, so it's way better than either using Bellman-Ford N times or using
Floyd-Warshall. The second reason this running time is so
cool is that it matches the running time we were getting already in the special
case when edge links were non negative. so this is very different than how we
were conditioned to think about the world when we talked about single source
shortage path problems. Remember, in those problems, we have Dexter's
algorithm which only handles non negative edge links but runs in near linear time
and there's no algorithm known for single source shortest paths that's near linear
that can handle negative edge links, the Bellman Ford algorithm certainly is not
near linear running time. That's Big O of N times N.
Johnson's Algorithm shows that while negative edge lengths are indeed an
issue, they can be handled in one shot using just one invocation of
Bellman-Ford. While the Bellman-Ford algorithm is
indeed quite a bit slower than Dijkstra's algorithm, it's only roughly a factor of
N slower. So one invocation of Bellman-Ford doesn't
change the overall running time when we already have to do N invocations of
Dijkstra's algorithm, even in the special case of the problem where all of the edge
lengths are non-negative. So that is why for all pairs shortest
paths we see a convergence in the performance of algorithms that solve the
problem in general, and algorithms that only solve the problem in the special
case of non-negative edge lengths. The missing piece to the correctness
argument is understanding why in general the modified edge links, the C prime E's
are guaranteed to be non-negative. We saw that they were non-negative in
this specific example, but we have not yet proved it in general.
We'll do that on the next slot. Assuming for the moment that, that is
true, that the modified edge links are indeed non-negative, and therefore, when
we invoke Dijkstra it will correctly compute shortest paths, we're pretty much
done. In particular, recall that we had a quiz
in the previous video where we analyzed the ramifications of re-weighting.
And we saw that if you re-weight using particular vertex weights, some P sub Vs.
Then, for a given choice of an origin u, and a given choice of a destination v.
Every single uv path has its length changed by exactly the same amount, by a
common amount. Namely, the difference between u as
vertex weight p sub u. And the destination v as vertex weight, p
sub v. So that means, when we invoke Dijkstra's
algorithm in step four. Indeed, gets the shortest paths correct.
The shortest path distances are incorrect.
But we know exactly how much they're off by.
They're off by Pu minus P sub v. And that is corrected for in step five.
So that's why assuming correctness of Dykstra's algorithm Which in turn relies
on non negativity of the modified edge links.
The end result of Johnson's algorithm is indeed the correct shortest path
distances. To finish the analysis of Johnson's
algorithm all that remains is to prove the following claim.
Which is that for every single edge of the graph, it's length after we do re
weighting is non negative. So the proof in fact is not hard.
It follows quite easily from properties of shortest path distances.
So fix your favorite edge E, let's say going from U to V.
The vertex weights are, by construction, just shortest path distances from the
vertex little s. Well remember S is the extra source
vertex that we added to the original input graph G.
So by the way we constructed the graph G prime, there is at least one path from
this auxiliary source vertex S to every other vertex.
So there is some shortest path from S to U, let's call it capital P.
By definition, the length of capital P has to be little p sub u.
It's a simple matter to obtain from this path capital P, which goes from S to U.
A path which goes from S all the way to V.
Namely, just concatenates the edge UV as a final hop.
The length of this path which goes from S to V is of course just the length
incurred going from S to U, Which is just P sub U, plus the length of the final hop
which is just the length of this edge, C sub U V.
Now this is just some old path from S to V.
The shortest path from S to V, can of course, only be shorter.
And only piece of V, the vertex way to V, is by definition, the length of the
shortest path from S to V. And now, we're good to go because the
modified length of this edge C. That is C prime sub E is just the
difference between the right hand side of this inequality and the left hand side.
So that's why the difference is guaranteed to be non negative.
Since this was an arbitrary edge it holds for all the edges.
That completes the proof in the analysis of Johnson's algorithm.
