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).
A Reweighting Technique
Loading...
Из курса от партнера Stanford University
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
436 оценки
Из урока
Week 1
The Bellman-Ford algorithm; all-pairs shortest paths.
Познакомьтесь с преподавателями
Tim RoughgardenProfessor
Computer Science
Let's now proceed to the final algorithm for
the all-pairs shortest path problem that we're going to discuss.
It's called Johnson's algorithm, and the algorithm shows something pretty amazing.
It shows that even in graphs with negative edge lengths, the all-pairs shortest path
problem can effectively be reduced to just N indications of Dykstra's algorithm.
Even though Dykstra's algorithm needs non-negative edge links.
So, this video will discuss the key idea behind Johnson's algorithm,
will then proceed to the algorithm itself.
And this idea is a way of using vertex weights to re-weight shortest path links.
When we began our discussion on the all pairs shortest path problem we observed
that the problem reduces to end indications of a suitable sub routine for
the single source version of the problem simply by iterating over all N choices for
the source vertex.
The running time you get from this reduction is evidently
N times the running time of the single source sub routine.
And the running time of the sub routine is going to depend on whether your graph has
non negative edge lengths or not.
If you're in the lucky case where the graph has non-negative edge lengths
you get to use Dykstra's algorithm which runs blazingly fast almost linear time
M the number of edges times log N.
If you're dealing with a graph with the general edge lengths,
then the running time was not so good.
It would be N times the Bellming Ford running time which itself is N M.
At the end of the day you get a running time of N M log N for
the non-negative edges case, or N squared m for the general edges case.
And now that we know about the [INAUDIBLE] algorithm which runs in big O of
N cubes time, there aren't a whole lot of reasons to care about this solution
in [INAUDIBLE] which runs Bellman-Ford end times except perhaps
the fundamentally distributed nature of that computation.
Johnson's algorithm remarkably shows that the same running time we get here for
the non-negative edge limit case, N times N times log N, we can get equally well for
graphs that have general edge lengths.
Specifically, Johnson's algorithm shows that the alt pair shortest
path problem in graphs with general edge lengths reduces to one indication
of the Bellman-Ford algorithm followed by an indication of Dexter's algorithm.
As we know, the Bellman-Ford algorithm runs in M times N time.
Any indications to Dexter's Algorithm is going to be N times M times Log N.
Putting it together we see that the N indications of Dexter Dominate
just barely.
So the overall running time we'll achieve is big O of N M log in.
Exactly the same running time we were getting for
the non-negative edge length of case.
So this should probably sound a little too good to be true.
How on Earth can we reduce the shortest path problem with general edge lengths to
the special case where all the edge lengths are non-negative.
Indeed this is a trick that we actually thought some about in part one for
those of you who are alumni of that course.
Suppose you have the single short sorted path routes and
you've got a graph with some negative entries.
A very natural instinct is to say, well come on, that can't be that big a deal.
Let's just shift the edge a bit so they become non-negative.
And then keep your passed.
So if you have some graphs with the most edge link as minus five,
why not just add five to the link of every single edge.
Now you have a new graph, non-negative edge lengths, and
you just run Dijkstra's algorithm.
Big deal.
So this quiz asked you to think about this edge shifting trick in general.
Suppose you have a graph and
there's a particular source S in destination T you're looking at.
And suppose you add some constant number,
capital M, to the length of every single edge of the graph.
Under what conditions will that preserve the shortest path between S and T.
All right, so the correct answer is C Of the listed conditions,
the only one that guarantees that adding a constant M to every edge length
preserves the shortest path between a pair of vertices S and T is that all
of the paths between that pair of vertices have the same number of edges.
Maybe the easiest way to see this is just with a simple example.
So consider this simple pic network where there's an S and a T and
there's two paths between them.
One with two hops each of cost one and one with one hop of cost three.
Now evidently in this graph the shortest
one is the one that goes threw the vertex V.
That one has length two the other one has length three.
Now suppose we add a fixed constant,
let's say the constant two to every one of these edges.
In that case the two edges on top their lengths increase to three.
The edge on the bottom,
its length increases to five and you'll see that after we've shifted
all the edge lengths we've actually changed what the shortest path is.
It used to be the two hop path on top.
Now it's the one hop path on bottom that has length five.
The two hop path on top now has length six.
So this shows that the answers A, B and D are all incorrect.
Why is C correct.
Well suppose it was the case that between the vertex S and
T every single path in the graph had exactly the number of edges.
Say every path had 12 edges.
Well then when you add a constant to every edges length, every path between S and T.
Their length goes up by exactly the same amount.
It goes up by 12 times M if each of the paths have 12 edges in it.
So if every single path between S and T goes up by exactly the same amount,
well then the shortest path remains exactly the same.
The ranking of the lengths of the various path that's exactly the same because we've
added exactly the same number to all of them.
So the broader point here is that if we want to find a transformation of
the lengths of a graph that reduces the general edge length case to
the non-negative edge length case,
we need to aspire toward transformations that preserve what shortest paths are.
And this transformation is not it.
There's no reason for you to expect that there'd be any useful transformations
of this form, any shortest path preserving transformations that are nontrivial but
such transformations do exist.
That's the re-weighting technique, which we'll start exploring in the next quiz.
So in this quiz we're getting you to think about one of our usual directed graphs.
Every edge has a length and the lengths can be arbitrary real numbers.
Here is the twist.
For each vertex v there's going to be a number p
sub v associated with that vertex.
Don't worry about where these P sub V's come from we'll discuss that later.
Just think of it as any old number.
Could be seven, could be minus five.
Whatever, just one number per vertex.
The key idea behind the reweighting technique is to use these end numbers
one weight per vertex, P sub V.
To use these end numbers to shift the edge lengths of the graph.
I'm going to use C prime to denote that these shifted or transformed edge lengths.
Here's the exact definition.
Consider an arbitrary edge E of this graph G.
Let's say the edge goes from the tail U to the head V.
The new length, C prime of E, is defined as the original length CE.
Plus the weights of these edges tail so plus P sub U,
minus the weight associated with these edges head that is minus P sub V.
So, for example, consider an edge from U to V, that original length is two.
And let's say the weights associated with its tail and head are minus four and
minus three.
Remember, these vertex weights can be arbitrary numbers, positive or negative.
Well then, the shifted weight, C prime, is going to be,
by definition, two plus minus four.
Minus, minus three.
This of course is just equal to one.
So that's the setup.
Here's the quiz question.
I want you to think about some fixed path, capital P.
Let's say it starts at a vertex S and ends at a vertex T.
Now capital P may or may not be the shortest path, I don't care.
It's just any old path starting at S, ending at T.
So suppose in the original network with the original edge length C sub E
the total length of this path P was capital L.
What is its new length L prime under these new edge lengths C prime.
So the correct answer is C.
Under the new edge links C prime,
the path key's link does not in general remain the same but
it shifts by a predictable amount namely difference between the node
weight associated with S the origin of the path and T the destination of the path.
This follows by a simple calculation.
To the new length of the path P is of course just the sum
over the modified edge lengths.
The sum over the c primes of the edges in P.
So now we just expand each term in terms of its definitions so remember
the new edge length C prime of E is just the original length CE plus the weight
associated with the edges tail, U minus the weight associated with its head, V.
Now consider a vertex other than S or T on this path,
some internal vertex on the path.
So such a vertex is going to be the tail of exactly one edge of P.
And it's going to be the head of exactly one edge of P.
So its vertex weight is going to show up with a coefficient of plus one once.
And that'll show up with the coefficient of minus one, one S,
obviously those two terms will cancel.
So the only vertex weights that matter when we evaluate the sum is the weight of
the origin S and the weight of the destination, T.
The S only shows up once and it shows up as a tail so
it's vertex weight shows up with a plus one contribution.
So that's where the Ps term comes from.
Symmetrically the destination T only shows up once with a minus one coefficient.
so that's where the minus T comes from.
So when the dust settles,
all that we're left with is the sum of the original edge links that we're using
the notation capital L for, plus this shift term, plus Ps of S, minus Ps of T.
All right, so
now that we've slogged through the algebra let me explain to you why we went through
that exercise, what is the potential application of this reweighting technic.
So what we've just learned about the reweighting technic.
Well, fix a graph and fix an origin vertex S and a destination vertex T.
What we just learned is that when you reweight using these vertex weights,
you shift every single ST path by exactly the same amount.
The length of every ST path, shortest or otherwise,
changes by exactly the quantity P of S minus P [INAUDIBLE] T.
So this is now starting to sound pretty cool,
because let's remember our first quiz.
In our first quiz, we explored what happens when you just
add a fixed amount capital end to every edge of a graph.
We noticed it doesn't work in the sense that it can change the shortest path.
Why can it change the shortest path.
Well, different paths have a different number of edges.
So if you add some fixed amount to each edge,
you change different paths by different amounts.
That can screw up the shortest path.
If you're lucky and all of the paths between an S and a T have exactly the same
number of edges, then you shift them all by exactly the same amount and
you preserve the ordering of the paths.
But what do we see here.
We see that under no assumptions whatsoever about what the paths
between S and T like, Note reweighting shifts every single path
from ST by exactly the same quantity, the difference between PS and PT.
Since reweighting changes the length of every path by exactly the same amount,
that means it preserves the shortest path.
Whatever was the shortest path previous is still the shortest path
after we've done re-weighting.
So what.
Why is this interesting.
Well, let's dream big.
Suppose we could actually come up with vertex weights that
transformed the problem into one that we don't know how to solve blazingly fast.
Into one that we do know how to solve blazingly fast.
That is, what if we can find vertex weights that change an arbitrary instance,
that in general has negative edge lengths.
Into a shortest path problem, where all of the edge links are now non-negative.
So if such a transformation existed, I hope that its use would be clear,
this would transform an instance of shortest path.
Where it seems like we're stuck with the Bellman-Ford algorithm because we start
with negative edge lengths.
And it transforms it into an easier one,
where we can apply Dijkstra's shortest path algorithm.
Now, this best case scenario should sound like a free lunch to you.
Why do we think we can do basically a trivial amount of work.
Just the simple shift of the edge lengths.
And transform a seemingly harder problem, shortest path with general edge lengths,
into an easier one, shortest paths with non-negative edge lengths.
The catch, of course, is to figure out which vertex weights to use.
How do you know the magical edge weights that transform the general edge lengths
into the non-negative ones.
Actually, more fundamentally, why do we even think.
think that these vertex weights exist.
No matter how you pick the vertex weights, it's impossible to
transform all of the edge links so that they become non-negative.
Well, it turns out, as long as the graph has no negative cycle,
which we know as essential to computer shortest paths.
If there's no negative cycle,
there do always exist, magical choices of the vertex width P sub V.
That, transforms all of the edge links to B non negative.
Now it's not trivial to computer them, you have to do some work.
But it's not a prohibitive amount of work.
In fact, one indication of the Bellman Ford Algorithm, will be sufficient.
Johnson's algorithm puts those ideas together, that'll be the next video.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
