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).
Optimal Substructure
Loading...
From the course by Stanford University
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
437 ratings
From the lesson
Week 1
The Bellman-Ford algorithm; all-pairs shortest paths.
Meet the Instructors
Tim RoughgardenProfessor
Computer Science
In this video, we'll start developing the Bellman-Ford algorithm
as an instantiation of the dynamic programming paradigm.
We'll develop it in the usual way, by understanding how optimal solutions must
necessarily be composed of optimal solutions to smaller sub-problems.
So let me just quickly review what we learned from the subtleties of
the previous video.
In particular, let me be precise about what I mean by solving the single-source
shortest path problem when the input graph can have negative edge costs.
So the input, as usual, is a directed graph.
Every edge has an edge cost, c sub e.
We're allowing those edge costs to be negative.
And we're given a source for text s.
So what do we want to compute?
Well, ideally, we'd like to compute the shortest path distance from s to all other
destinations v, where as usual,
the length of the path is just the sum of the edge costs.
Now, in a previous video, we discussed how this goal is problematic for
input graphs that have a negative cycle.
If you allow cycled paths to contain cycles then this isn't even defined.
The, in some sense, shortest path length is minus infinity.
And if you don't allow cycles, then it's computationally intractable and
would be a hard problem.
So if you fail to compute shortest paths, then, at least, tell us an excuse.
Output a negative cycle in the input graph as the reason for
your failure to compute shortest path distances.
So for this video, I'm just going to develop the Bellman-Ford algorithm for
input graphs that do not contain negative cycles.
And, of course, these are the cases in which we better actually
output the correct shortest paths.
Once we've got the Bellman-Ford algorithm up and running for
input graphs that do not have negative cycles,
we'll see that it's a fairly easy matter to extend it to the general case.
And for input graphs that have negative cycles, we'll be able to
output such a cycle without affecting the running time of the basic algorithm.
So with an eye toward a dynamic programming algorithm for
the shortest path problem, let's start thinking about optimal substructure,
the way in which optimal solutions, that is shortest paths, must necessarily be
composed of optimal solutions, that is shortest paths to smaller sub-problems.
Now, the formal optimal substructure limit is going to be a little bit cumbersome
to state.
So let me just spend a slide kind of telling you what the deal is,
how to think about it.
It's often tricky to figure out how to apply the dynamic programming paradigm to
graph problems.
One of the reasons for that is that graphs aren't really naturally
sequential objects, they're not ordered in any obvious way.
We're just given some unordered set of vertices, and some unordered set of edges.
Now, one special case,
of course, would be path graphs, our very first example of dynamic programming.
There, there was an obvious ordering on the vertices of the graph.
But unlike, say, alignments, sequences, where again there's an obvious ordering
from left to right, in a graph problem, it's not so clear how to order things.
For this particular graph problem, however, it seems like we've got something
going for us, which is the sequentiality of our output.
Right? Paths are certainly sequential objects.
So that gives us hope we can state and
prove an optimal substructure lemma, talking about how optimal solutions,
shortest paths, must be built up from, in some sense, smaller shortest paths.
Unfortunately, it's still far from obvious how to really define smaller and
larger sub-problems.
So, for example, you'd love to have some intelligent ordering on which you
process the possible destinations v.
But it's not at all clear how to do that without knowing the shortest path
distances in the first place.
So this is a subtle issue that I encourage you to think
hard about in the privacy of your own home, so you can better appreciate what's
non-trivial about the Bellman-Ford solution.
So the key idea in the Bellman-Ford algorithm, and
it's a good one, is to introduce an additional parameter that gives us
an unambiguous definition of sub-problem source.
So what this parameter is going to do, for a given destination v,
is it's going to control how many edges
we allow in paths from the source s to this destination v that we're looking at.
To explain this, let's look at the following green graph that has
five vertices on the right-hand part of the slide.
So in the Bellman-Ford algorithm, we're going to have one sub-problem for
each possible destination, and
each possible restriction on the number of edges in a path.
So, for example, suppose we're looking at s and we're looking at destination t.
And we think about paths that only have two edges or less.
Well, in that case, the shortest path length,
subject to that constraint from s to t in this graph, has the length of four.
The bottom path, which has three edges, is not an option,
we're only permitting two edges or less in this current sub-problem.
Now, if we bump up the edge budget to three,
then the corresponding shortest path distance drops from four, to three.
Because all of a sudden, we can make use of this three-hop path on the bottom.
And again, the point here is that it gives us an unambiguous
notion of sub-problem size.
The more edges you're allowed to use in your paths,
from a source to a given destination, the bigger that sub-problem.
All right, so that discussion was deliberately vague, to give you some
context for the following formal statement of the optimal substructure lemma.
So we're going to go ahead and state and
prove this optimal substructure lemma in full generality.
We're going to be working with arbitrary input graphs,
they might have a negative cycle, they might not.
So like all of these optimal sub-structure lemmas,
the statement gonna's have the form that the optimal solution to a sub-problem has
to be one of a small number of candidates that are composed in simple ways from
optimal solutions to smaller sub-problems.
So how do we index a given sub-problem?
Well, there's going to be a destination v, that we care about.
And, as we said in the last slide, there's going to be a budget on
how many edges you're allowed to use in a path from s to v.
And we're going to use i to denote that budget.
So for every possible destination v, and so for every possible edge budget,
there's going to be a positive integer, 1 or bigger.
Suppose that p is an optimal solution then.
Meaning, amongst all paths that start at s, that end at v, and
that contain, at most, i edges.
Amongst all of those paths, p has the minimum sum of edge cost,
the minimum length.
So a subtle point, because we're proving this lemma in its full generality,
that is also for input graphs that might have negative cycles,
we need to go ahead and allow this path p to use cycles if it wants,
including potentially to use a negative cycle multiple times.
That is allowed.
Notice we're not worried about this path using this cycle an infinite number
of times, because we have a finite budget, i, on how many edges it can contain.
So with that setup, what are the possible candidates for
what capital P could possibly be?
We're going to have our usual trivial case 1,
which is that if this path P doesn't bother to use up its full edge budget,
that is if it has (i-1) edges or less, well then, naturally,
P better be the shortest s-v path that has at most (i-1) edges.
So the non-trivial case is when the shortest path with the most i
edges from s to v actually uses its full budget, uses all i of its edges.
So now, by analogy, with all of our previous dynamic programming algorithms,
where we think about plucking off the final part of an optimal solution,
here we're going to pluck off the final edge from the path p.
What do we get?
Well, we get a path with one fewer edge.
So that's good, it's going to correspond to some smaller sub-problem,
because it has at most i-1 edges.
On the other hand, notice that if we take a path from s to v and
we pluck off the final edge, we get a path from s to somewhere else.
So we're going to call that somewhere else w.
So plucking off the final edge from capital P gives us a path, P prime,
that starts at s, that ends at w, that has at most i minus 1 edges.
And I hope you can guess that the claim is that it's not just any old path from
s to w with the most i minus 1 edges.
It is, in fact, a shortest such path.
Now, in this case, too, notice that, we, of course,
know that p prime has exactly i minus 1 edges.
Not nearly at most, i minus 1 edges.
But it's going to be useful to have the stronger assertion claimed here, that
P-prime is optimal amongst all paths that have i minus 1 edges, or possibly fewer.
All right, so this is one of those lemmas that's actually harder to state
than it is to prove.
So let's just quickly sort of talk through the proof.
It's the same as the previous optimal substructure lemmas that we've seen.
Case one is totally trivial,
it's the obvious contradiction that we've seen in many of our other case ones.
Case two is going to be one of our usual cut-and-paste contradictions.
So suppose there was some path Q better than P-prime,
that is Q starts at s, ends at w, contains (i-1) edges or
less, and the sum of its edge costs is even smaller than that of P-prime.
Well then, if we just tack on the final hop of p, that is, the edge wv,
we get a path that starts at s, that goes to v, that has the most i edges.
And the total sum of edge costs,
in this path q plus wv, is strictly less than that in the original path P.
But that contradicts the purported optimality of p,
amongst all paths starting at s, ending in v, and having the most i edges.
So that's the proof of the optimal sub-structure lemma.
It's simple enough.
And as usual, the next step is going to be to compile this lemma into a recurrence,
where informally, what the recurrence is going to do is brute-force search
amongst the possible candidates for the optimal solution.
So to make sure you understand what just happened, let's move on to a quiz.
And the question is, for a given destination v of some input graph,
how many candidates are there for
the optimal solution of a sub-problem that involves v?
The correct answer is the second one.
The answer depends on which destination v you're talking about, and
what governs the number of sub-problems is the in degree of this vertex.
That is, the number of edges of the input graph that have v as their head.
Why is this true?
Well, case one contributes one possible candidate.
It's possible that for a given i and a given v, all you do is inherit the optimal
solution to destination v, with a budget of one fewer edge.
Case two may seem like only one other candidate, but actually case two comprises
a number of them, one for each choice of that final hop w, v.
Specifically for a given choice of w, that contributes a candidate
optimal solution that's the shortest path from s, to that choice of w
that uses the most i minus 1 edges, plus that edge wv tacked on.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
