The reason it matters whether or not the edge costs are all non negative or not is

it governs which single source shortest path team we get to use.

So if, the happy case, all edge costs are not negative, then we get to use

Dijkstra's algorithm as our work horse. And remember Dijkstra's algorithm is

blazingly fast. Our heap based implementation of it Ray M

time M log N. So if you run that N times you're running

time is naturally N times M times log N. So in the sparse case this is going to be

N squared log N. In the dense this is going to be N cubed

log N. [SOUND] So for sparse graphs, this

frankly is pretty awesome. You're not going to really do much

better, than running Dijkstra n times, once for each choice of source, of the

source vertex. The reason is, we're responsible for

outputting n squared values, the shortest path distance for each pair uv of

vertices. And so here, the running time is just

that n squared, times an extra log, log factor.

[SOUND] The situation for dense graphs, however, is much murkier.

And it is an open question to this day whether there are algorithms

fundamentally faster than cubic time for the all pair shortest paths problem in

dense graphs. If you wanted to try to convince somebody

that maybe you couldn't do better than cubic time, you might argue as follows.

There's a quadratic number of shortest path distances that have to be computed.

And for a given pair, u and v, the shortest path might well have a linear

number of edges in it. So, surely, you can't compute the

shortest path between one pair better than linear time.

So then the quadratic number is going to have to be cubic time.

However, I want to be clear. This is not a proof.

This is just a wishy washy argument. Why is it not a proof?

Well, for all we know, we can do some amount of work which is relevant

simultaneously for lots of these shortest path problems.

And you don't actually have to spend linear on average time for each.

As a tale of inspiration, let me remind you about matrix multiplication.

If you write down the definition of what it means to multiply two matrices, you

look at the definition and it just seems like it's an obviously cubic problem.

It just seems like by definition, you have to do a cubic amount of work.

[SOUND] Yet, that intuition is totally wrong.

Beginning with Strassen, and then many following algorithms, we now know that

there are algorithms for matrix multiplication, fundamentally better than

the naive, cubic time algorithm. If you have a, nontrivial approach to

decomposing a problem, you can eliminate some of the redundant work, and do

better, than the straightforward solution.

Is a Strassen-like improvement possible for the all pair shortest paths problem?

[SOUND] Nobody knows. Now let's discuss the general case in

quick graphs that are allowed to have negative edge lengths.

So in this case we cannot use Dikstra's algorithm as our workhorse, as our single

source shortest path subroutine. We have to resort to the Bellman-Ford

algorithm instead because that's the only one of the two that accommodates negative

cost edges. Remember the Bellman-Ford algorithm is

slower than Dikstras algorithm, the running time down that we proved was O of

M times N. If we run that N times we get a running

time of M times M squared. How good is the running time of N squared

M? Well, if the graph is sparse, if M is

theta of N, then this is cubic in N. And if the graph is dense, M is theta of

N squared, we're now seeing our first ever for this course, quartic running

time. Hey and I hope that you're not really

especially happy with the cubic running time down for the sparse graph case, but

now when we're talking about quartic running time, now this just really seems

exorbitant. And so hopefully you're thinking there's

gotta be a better approach to this problem than just running Bellman-Ford

N-times in the dense graph case. Indeed, there is: the Floyd-Warshall

algorithm, we'll start talking about it next video.