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.