Johnson's Algorithm For Sparse Graphs

Johnson's algorithm finds shortest paths between all pairs in $O(V^2lgV + VE)$ time. Johnson's uses both Dijkstra and BF as subroutines. It uses the technique of reweighting, which works as follows. If all edge weights w in a graph G=(V,E) are nonnegative, we can find shortest path between all pairs of vertices by running Dijkstra once from each vertex; with the Fibonacci-heap min-priority queue, the running time of this all-pairs algorithm is $O(V^2lgV + VE)$. If G has negative-weight edges but no negative cycles, we simply compute a new set of nonnegative edge weights that allows us to use the same method. The new set of edge weights $w^*$ must satisfy two important properties:

• For all pairs of vertices u,v $\in$ V, a path p is a shortest path from u to v using weight function w if and only if p is also a shortest path from u to v using $w^*$
• For all edges (u,v), the new weight $w^*$(u,v) is nonnegative.

We can process $w^*$ in O(VE) time.

Lemma: Reweighting does not change shortest paths

Given a weighted, directed graph G and a weight function w : E -> R, let h : V -> R be any function mapping vertices to real numbers. For each edge (u,v) $\in$ E, define

$w^*$(u,v) = w(u,v) + h(u) - h(v)

Let p = { $v_0, v_1, ..., v_k$ ) be any path from $v_0$ to $v_k$ . Then p is a shortest path from $v_0$ to $v_k$ with weight function w if and only if it is a shortest path with weight function $w^*$.

That is, w(p) = $\delta (v_0, v_k)$ if and only if $w^* (p)$ = $\delta^* (v_0, v_k)$. Furthermore, G has a negative-weight cycle using weight function w if and only if G has a negative-weight cycle using weight function $w^*$.

Producing Nonnegative weights by reweighting

The next goal is to ensure that the second property holds: we want $\delta^* (u,v)$ to be non negative for all edges (u,v) $\in$ E. We make a new graph G' =(V',E) where V'=V U {s} for some new vertex s not in V and E' = e u {(s,v) : v in V}.

We extend the weight function w so that w(s,v) = 0 for all v in V. Note that because s has no edges that eneter it, no shortest path in G', other than thiose with source s, contain s. Moreover, G' has no negative-weight cycles if and only if G has no negative weight cycles.

Now suppose that G and G' have no negative-weight cycles. Let us define h(v) = $\delta (s,u)$ for all v in V'. By the triangle inequality we have h(v) <= h(u) + w(u,v) for all edges (u,v) in E'. Thus, if we deifne the new weightrs w* by reweighting according to the lemma equation, we have w*(u,v) = w(u,v) + h(u) - h(v) >= 0 and we have satisfied the second property.

Computiong all pairs shortest paths

Jonhson compute the all-pairs shortest path using BF and Dijkstra as subroutines. It assumes that the edges are stored in adjacency lists. The algorithm returns the usual |V| x |V| matrix D = $d_{ij}$ WHERE $d_{ij}= \delta (i,j)$ or it reports that the input graph contains a negative-weight cycle.

JOHNSON(G,w)
    compute G', where G'.V = G.V U {s}, G'.E = G.E U {(s,v) : v in G.V} and w(s,v) = 0 for all v in G.V
    if BF(G', w, s) == FALSE
        print "Input has negative weight cycle"
    else for v in G'.V
        set h(v) to delta(s,v) computed by BF
        for (u,v) in G'.E
            w*(u,v) = w(u,v) + h(u) - h(v)
        let D be a new nxn matrix
        for u in G.V
            run DIJKSTRA(G, w*,u) to get delta*(u,v) for all v in G.V
            for v in G.V
                d_uv = delta*(u,v) + h(V) - h(u)
        return D