In this next sequence of videos, we're going to revisit the single source
shortest path problem. This is a problem that we already solved
using Dijkstra's greedy algorithm. Now let's see what the dynamic
programming paradigm can do for us for the same problem.
Let me just quickly remind you the definition of the problem, what's the
input, what's the output. We're given a graph.
And when we talk about shortest path, we're going to be discussing only
directed graphs. Each edge of the graph has a length,
which we're going to denote by c-sub-e. And one vertex which we'll denote by a
little less is designated as the source vertex.
We're going to assume that the graphs are simple.
That is, there are no parallel edges. The reasoning is the same as the minimum
spanning tree problem if you had a bunch of parallel edges.
Since we only care about the shortest path, you may as well throw away all of
the copies of an edge except for the one that has the smallest length.
The responsibility of an algorithm for this problem is to compute the length of
a shortest path from this source vertex S to every other possible destination V.
And always, when we talk about the link of a path, we mean the sum of the edge
costs, of all of the edges that are in that path.
For example, if the cost of every edge was one, then we'd just be talking about
the hob count, and that's a problem that's solved using breath per search.
But in general in this single source shortest path problem, we're interested
in edges, that has possibly wildly different links from each other.
So let's now review our existing solution for the problem Dijkstra's algorithm.
Review its pros and its cons. The Dijkstra's algorithm is a great
algorithm. If you have a graph and it fits in your
computer's main memory and all the edge costs are non negative, if you implement
Dijkstra's algorithm using heaps, you will get a blazingly fast and always
correct shortest path algorithm. Part one of this course we explained an
implementation using heaps that runs in Big O of M times login time.
Where as usual M is the number edges and N is the number of vertices.
And this implementation is almost identical to the one we discussed earlier
in this course for prims algorithm computing the minimum of a spanning tree.
It turns out you can get an even better acetonic running time, at least
theoretically, a running time of M. Plus and login if you use a more exotic
type of data structure but let's for now just think of this as the line in the
sand big o of m login using dice wishin algorithm on a graph with non negative
edge lengths. So given what a great algorithm
Dijkstra's algorithm is, on what basis could we reject it and study any other
shortest path algorithm? Well, there's two drawbacks we've
mentioned before, let me reiterate them now.
So first of all if you're working with a graph where some of the edge costs can be
negative, then the output of Dijkstra's algorithm need not be correct.
The correctness relies on the non-negative edge cost assumption.
We saw concrete examples of this both back in part one of the course, but also
in this course when we first started talking about greedy algorithms and we
discussed to their ubiquitous incorrectness.
Now frankly, for many of the applications of shortest path algorithms you're never
going to run into negative edge lengths. If you are implementing, for example, a
program that computes driving directions, whether you're doing it in miles or in
time, you're not going to have negative length edges, at least until we get
finally get around to inventing those time travel machines.
But not all applications of the shortest path problem are so literal and involve
literally computing some path in space from some point A to some point B.
More abstractly, the problem is just helping you find an optimal sequence of
decisions. Imagine you were managing a bunch of
financial assets, for example, and you were modeling a single transaction as an
edge in a network that takes you from one particular inventory to another.
When you sell stuff, that might generate positive revenue and correspond to a
positive edge length, but when you buy stuff then, of course, you have to spend
money and that can correspond to a negative edge length.
So the second drawback which we mentioned in the intro video for this course, is
that dijkstra's algorithm seems highly centralized.
Now, that's not a problem if you just are destroying the entire graph in the main
memory of one machine, but if you're talking about routing in the interenet.
Well it's totally impractical for a router to have a up to date complete map
of the entire internet to compute routes locally and so that motivates looking at
a different shortest path algorithm, which is better suited for distributed
routing. So we're going to be able to address both
of these drawbacks in one fell swoop via the Bellman-Ford algorithm, which will be
yet another instantiation of the dynamic programing algorithm design paradigm.
This Bellman Ford algorithm, despite predating the earliest version of the
ARPAnet by a good ten years, nevertheless does form the basis for modern day
internet routing protocols. Of course there's a lot of engineering
steps that you need to go from the abstract Bellman Ford algorithm to
practical solution internet routing. We'll discuss that a little bit in a
separate video, but this really is where it all gets started.
So before we start developing the Bellman Ford algorithm, we need to take care of
some subtle preliminaries. We need to be clear about how we're
defining shortest paths in the presence of negative edge costs and in particular
in the presence of negative edge, negative cost cycles, that is a directed
cycle of edges where the sum of the edge costs is less than zero.
You can think for example about this green cartoon I've drawn off on the right
where somewhere embedded in this graph is a directed cycle that has four edges.
Some of the edges in the cycle have negative cost, some have positive but on
balance the cycle has negative overall cost, cost minus two if you traverse all
four of the edges. So let's think about how we should define
the shortest path from the source vertex S to some destination V in a graph like
this. Do, in particular, do we allow cycles in
the path or not. So first let's think through the
ramifications of allowing the paths to include cycles.
So this proposal actually doesn't make sense.
In that generally there will be no shortest path from S to V if you allow
cycle traversals. The reason being that if you have a
negative cycle like this one of overall cost minus two in the screen graph, and
you can actually reach it from the source S, then for every path you can actually
find another path which is even shorter. You traverse the directed cycle one more
time. The path overall path link drops by
another minus two, and there's nothing from stopping you from doing this over
and over and over again. So either the shortest path you can think
of it as being undefined. Or you can think of it as being sort of,
minus infinity in the limit. So if permitting our path to have cycles
didn't work, why not we explore the option where we forbid cycles in our
paths? So this version of the problem is
perfectly well defined. It's a totally sensible computational
problem, which you might well want to solve.
The issue here is much more subtle. The issue is that this problem is what's
called np complete, so that's something we'll discuss much more next week.
But the bottom line is these are intractable problems.
There are no known computational efficient, no known polynomial-time
algorithms for np complete problems. And this, unfortunately, is one such
problem. Computing shortest cycle-through paths in
the presence of negative cycles. So a bit more precisely, if you came up
with a guaranteed correct and guaranteed polynomial time algorithm, that was
computed shortest path and presence of negative cycles, the, a consequence would
be what's called P = NP. And that's something we'll discuss a bit
more formally in a later video. But, certainly if you came up with such
an algorithm you should report immediately to the Clay Institute.
They would have a $1,000,000 prize awaiting for you for such an algorithm.
So for those of you that are already familiar with NP completeness, it would
be an easy exercise to prove that this problem is NP hard.
It would just be a reduction from the Hamiltonian path problem.
So it seems that we are stuck between a rock and a hard place.
If we allow cycles in our paths, we don't get a meaningful problem.
We get something that doesn't make sense. If we exclude cycles, we get a perfectly
meaningful, but unfortunately computationally intractable problem.
So here's how we're going to proceed, we're going to focus for now, just on
graphs that do not have negative cycles. We will of course allow individual edges
to be negative, but we're going to insist for the moment that every single
directive cycle of the input graph has overall non negative length.
So we can have some positive edge cost, some negative edge costs.
But overall it has to be non negative. Now I don't blame you if this assumption
bothers you, but the good news is, as we'll see, the Bellman-Ford Algorithm
effortlessly checks whether or not this condition holds.
It effortlessly detects a negative cycle in the input graph if one exists.
So the version of the shortest path problem that Bellman Ford Algorithm is
going to solve will be the following. Given an input graph which has.
Negative edge costs. It may or may not have a negative cycle.
The Bellman Ford algorithm will either correctly compute shortest paths from the
source to all of the destinations just like you wanted, or it will punt, but it
will offer you a good excuse for why it punted.
It will show you a negative cycle in the input graph and of course computing
shortest path is intractable in the presence of a negative cycle so with
Bellman Ford you have to sort of let it off the hook in that case.
Okay? So it will give it an input graph either
it will show you a negative cycle or it will give you all of the shortest path
distances. That's the guarantee we're going to
strive for. So I'm going to end this video with a
quiz helping you understand why this hypothesis of no negative cycles might be
useful in an algorithm. So for now I just want you to think about
suppose I promised you that an input graph had no negative cycles.
And the question is how many hops, how many edges, are sufficient to guarantee
that you found the shortest path between S and some given destination phi.
So the correct answer is A and this is one of the main reasons the no negative
cycle hypothesis is useful it gives you control over how many edges are necessary
to ensure that you've got the shortest path.
So specifically suppose you had a path between some S and some V that had at
least. N edges.
Well if we have at least ten edges it means the path visits at least, N+11
vertices. There's only N vertices, so if you visit
at least, N+11, that means you visit one vertex twice, say X.
So, that means you have a cycle inside your path that goes from X back to X
again. Now, if you rip out this cycle, if you
just delete those edges you get another path from S to V and because, this
directed cycle as they all are, must be non negative.
The total length of some of the edge cost has only gone down, by removing this
cycle, so you show me, Path from s to the u with the least end edges I will show
you a path with fewer edges and that is at least as short could only be short so
that shows you that the shortest path or a shortest path has our most n minus one
edges which is the answer to the quiz.