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.