We're now well positioned to state Johnson's algorithm in its full

generality. The input as usual is a directed graph G.

Each edge has a edge length C sub E, it could be positive or negative.

The input graph G may or may not have a negative cost cycle.

As usual, when we talk about solving a shortest path problem we mean that if

there is no negative cost cycle, then we have no excuse. So we better correctly

compute all of the desired shortest paths.

In this case between all pairs of vertices.

If there is a negative cost cycle, we're off the hook.

We don't have to compute shortest paths, but we.

need to correctly report that the graph does indeed have a negative cost cycle.

Step one is the same hack that we used in the example.

We want to make sure that there's a vertex from which we can reach everybody

else. So let's just add a new one that by

construction has that properties. So we add one new vertex to little s, we

add N new edges. One from s to each of the original

vertices and each of those new N edges has length zero.

We're going to call this new, bigger graph g prime.

The second step, just like in the example, is to run a shortest path

computation using this new vertex S as the source.

Since the graph G in general has negative etch cost, we have to resort to the

Belmont Ford out rhythm to execute the shortest path computation.

Recall that the Bellman-Ford Algorithm will do one of two things.

Either it will correctly compute the shortest path distances that we're after,

from the source vertex S to everybody else, or it will correctly report.

That the graph it was fed, namely g prime, contains [SOUND] a negative cost

cycle. Now, if g prime contains a negative cost

cycle, that cycle has to be the original graph, g.

Our, the new vertex, s, that we added, has no incoming arcs at all, so it

certainly can't be on any cycle, [SOUND] so any negative cycle is the

responsibility of the original graph, G. [SOUND] Therefore if Bellman-Ford finds

us a negative cost cycle, we're free to just halt and correctly report that same

result. So from here on out, we can safely assume

that G and G prime have no negative cost cycle, and therefore that the

Bellman-Ford algorithm did indeed correctly compute shortest path distances

from S to everybody else. As in the example, we are going to use

these shortest path distances, [SOUND] all of which are finite by construction.

As our vertex weights, our P sub Vs. We then form the new edges lengths, the C

primes, in the usual way. C prime of an edge E going from U to V is

the original length CE plus the weight of the tail P sub U minus the weight of the

head P sub V. In the example, we saw that the new edge

length C prime are all non-negative. We will shortly prove that, that property

holds in general. If you define your vertex weights in

terms of shortest path distances from the new vertex S to everybody else in this

augmented graph G Prime it is always the case that your new edge lengths would be

non-negative. Assuming that for now, it makes sense to

use Dijkstar's algorithm N times, once for each choice vertex to compute all

pairs shortest paths in the graph G with the new edge length C prime.

In a particular iteration of this four loop.

Say, when we're using the vertex u as the source vertex.

We're going to be computing n of the shortest path distances that we care

about. From u to the various n possible

destinations. And let's call those shortest paths

computed by Dijkstra in this iteration d prime of u, v.