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).
The Basic Algorithm I
Loading...
來自 Stanford University 的課程
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
298 個評分
從本節課中
Week 1
The Bellman-Ford algorithm; all-pairs shortest paths.
與講師見面
Tim RoughgardenProfessor
Computer Science
Now that we understand the optimal substructure present in shortest paths,
we can follow our usual dynamic programming recipe to arrive at the basic
version of the Bellman-Ford algorithm. Let's compile our optimal substructure
lemma into a recurrence of formula that says how the optimal solution of a given
sub problem depends on that of smaller sub problems.
I'll use the notation capital L sub I V to denote the optimal solution value of
the corresponding subproblem. Subproblems being indexed by two
parameters, one V, that's the destination we're interested in, in this subproblem.
In the second one is the budget I on the number of edges that are permitted in
paths from S to V in this subproblem. So, a few details.
First of all, remember that in the last video we proved the optimal substructure
limit in general for general graph G, which may indeed have negative cycles.
For that reason, we have to allow cycles in shortest paths from S to V.
We're not concerned about the cycle being traverse an infinite number of times,
because we have this finite budget I and the number of edges that we permit.
I also need to explain what I mean in the case that there are no paths from S to V
within most I edges, and indeed when I is very small, that will in fact be the case
for many destinations V, so if there's no way to get from S to V using I hops, we
just define LIV to be plus infinity. And as usual, in the recurrence which is
going to be defined for every positive integer I and every possible destination
V we're just going to state that the optimal solution value for the sub
problem is the best of the possible candidates identified in the optimal
substructure lemma. That is, capital L sub IV, the optimal
solution value for the sub-problem with parameters I and V is the best of all of
the possibilities. So let me start with a minimum to take
the best of the case one candidate and the case two candidate.
The case one candidate is simple enough. One option is always just to inherit the
best path we found from s to v that uses only I-1 edges or less.
In case two, you'll recall from the quiz at the end of the last video really
comprises a number of sub cases, one for each choice of the finally hop.
So here we're going to have another minimum ranging over all possible edges
WV. For a given choice of that last hop.
The shortest path length is going to be the shortest path from s to that choice
of w that uses the most I minus one edges.
And then of course we also we incur the edge cost of the final hop, w comma v.
Correctness, as usual, follows immediately from the optimal substructure
lemma. We know these are the only candidates,
and by the definition of the recurrence, we pick the best one.
Because the optimal substructure lemma has been proven.
Whether or not g has a negative cycle, this recurrence is correct for all
positive values of I, whether or not g has a negative cycle.
So now, let's see how it's useful to assume that the input graph g does not
have a negative cycle. So we had a quiz not too long ago, that
discussed the use of the no negative cycles hypothesis.
In particular, we argued that N-1 edges are always enough to capture a shortest
path, between S and any possible destination.
Why? Well, suppose there's no negative cycles,
picks a destination V, show me a path that has at least N edges.
If it has at least N edges, then it visits at least N plus one vertices.
There's only N vertices, so the path must visit some vertex twice,
and in between two consecutive visits of a given vertex that's a directed cycle.
My hypothesis? There are no negative directed cycles,
they're all non negative. So if I throw out this directed cycle from this path, I
get a new path to the same destination V and it's overall length has only gone
down. Discarding cycles only makes paths
shorter. That's why there's a shortest path with, with no repeated vertices,
that is with at most n minus one edges. So what does this observation have to do
with our recurrence? Well it tells us, when you only need to
compute the end recurrence, evaluate sub problems for values of I up to n minus
one. There is no point in giving a sub problem
a budget bigger than n minus one edges if there are no negative cycles.
It's not going to be useful. You're guaranteed to have already found
the shortest path by the time I has gone as large as n minus one.
So, to make sure this point is clear, let me just formally write down the
subproblems that we're going to solve in the Bellman-Ford algorithm, and which are
going to be sufficient to correctly compute shortest paths for input graph g
that do not have negative cycles. The subproblems are simply to compute the
shortest path links capital L sub of IV. Of course, for all destinations, we're
responsible for ultimately computing shortest paths to every destination V,
and for all relevant choices of the edge budget I.
And so the base case is going to be when I equals zero, and we just said it has to
go up as n minus 1, and no further. And this is actually a pleasingly
parsimonious collection of sub-problems. It may strike you actually kind of a lot,
because there is a quadratic number, or there's N choices for the destination V,
and then I is rank taking on N different values.
But remember, unlike all the other problems we've been talking about, the
output of this problem is linear size. We're suppose to output a number for each
destination V. So, we really only have a linear number
of sub-problems for each statistic we're responsible for computing,
and that's as good as we've had on any of our other programming algorithms.
So now it's a simple matter to write out the pseudo-code of the justifiably famous
Bellman-Ford algorithm Because there are subproblems that are indexed by two
parameters, the edge budget I and the decimation V, we are going to have a
two-dimension array A. Remember that we're measuring sub-problem
size via the edge budget I. That's sort of the great idea in the
Bellman-Ford algorithm, to introduce this edge budget to control sub-problem size.
So the base case is when I equals zero, and then we're talking about getting from
S to some vertex V, using zero edges. Okay, well if V happens to equal S, then
you can do it with the empty path, and the length of the empty path is zero.
But if V is any vertex other than S, then, of course, you can't get from S to
V using zero edges, and remember in that case,
we define the optimum value solution to be plus infinity.
So now we move onto are customary double four-loop, one four-loop for each of the
indices that a nexus R array A. But actually, what's interesting is
unlike most of the dynamic programming algorithms we're discussing, here the
order of the four-loop matters. You can not pick arbitrarly.
You really need to make sure that you have all the smaller subproblems solved
by the time you need them. That means the outer four-loop should be
indexed by the subproblem size I. So, as we discussed, we're not going to
bother letting I range above n minus one. That's going to be sufficient for in the
case where there are no negative cycles, and for each choice of I, we solve all of
the corresponding sub problems, all destinations v.
For each choice of I and V, of course, we just write down in code the formula that
we stated in the recurrence. So as I'm sure you recall, case one
furnishes one possible candidate. It's always an option to just inheret, the
shortest path from S to V that you computed using only, I-1 edges.
Alternatively from case two, there's also one candidate furnished for each twist of
the final hop, so for each edge, that ends at V, for each choice W comma V,
there's an option of taking a shortest path from S to W, that uses only, I minus
1 edges, and tacking on that final edge, WV.
And as we've discussed, if it just so happens that the input graph G has no
negative cycles, then this algorithm will indeed terminate with a correct shortest
path from S to all of the destinations. Those answers will be lying in wait for
you, in the biggest subproblems, the A N minus 1 V's.
So that's correctness as usual. It follows primarily from the optimal
substructure lemma, but in this case also the hypothesis of no negative cycles
guarantees that taking I equal N minus one is large enough to actually capture
the final answers. So we'll talk about the running time of
the Bellman-Ford algorithm in a sec, but first let's just go through a quick
example to make sure all of this makes sense.
