所有对最短路径：Johnson算法

1. Introduction

In this tutorial, we’ll discuss Johnson’s algorithm. Along with Floyd-Warshall, it’s one of the algorithms for finding all-pairs shortest paths in directed and undirected graphs. Johnson’s algorithm shows good results for sparse graphs, while Floyd-Warshall is better for dense graphs.

2. Preliminary Notes

For our discussion, we assume we have a graph G=(V, E) . is the set of vertices of size , and is the set of edges of size . is a directed graph, and there are no negative-weight cycles in .

While negative-weight edges are allowed, there must not be negative-weight cycles. The reason is Johnson’s algorithm uses Bellman-Ford and Dijkstra’s single-source shortest paths algorithms (SSSP) as subroutines.

SSSP algorithms don’t work when negative-weight cycles are present. Generally, no shortest paths algorithm makes sense when there’re negative-weight cycles.

3. Algorithm Description

The idea of Johnson’s algorithm is to run Dijkstra’s algorithm for each vertex in $\boldsymbol{G}$ . Unfortunately, that’s workable when there’re no negative-weight edges, as Dijkstra’s algorithm is designed for only non-negative edge weights. To overcome the limitation, the Bellman-Ford algorithm is used to re-weight the edge weights, so there are no negative edge weights.

One can think of an alternative to using the Bellman-Ford algorithm for making the edge weights positive. What if we added the minimum negative edge weight to all the edge weights? That makes the edge weights non-negative, but the idea isn’t workable. If we fix a vertex pair (u, v) , multiple paths may be from to . When these paths contain a non-equal count of edges, the path weights get modified differently, so a non-shortest path may become shortest in this way.

Here, we’ll provide a step-by-step explanation of Johnson’s algorithm.

3.1. A New Vertex

We add a new vertex, , to the graph. Then, we connect with all the vertices in the graph. The edges are directed from , and the new edge weights are zero. Thus, $\boldsymbol{s}$ with the new edges doesn’t modify any existing shortest path between the original vertices of the graph.

3.2. Running Bellman-Ford Algorithm

Next, we run the Bellman-Ford SSSP algorithm for . After this step, we get the shortest paths from to each graph vertex. Let’s keep the shortest paths in distance[] array, where distance[v] is the shortest path from to .

3.3. Re-weighting the Edges

Then, we modify the edge weights. Assume the weight of edge (u, v) is denoted by weight(u, v) , and the new weight of the same edge by newWeight(u, v) . Then, we define the new weights as:

newWeight(u, v) = weight(u, v) + distance[u] - distance[v]

The new weights are non-negative because for any edge (u, v) , $distance[v] \le distance[u] + weight(u, v)$ . The inequality follows from the fact that is the shortest path from to , and if was less than , then there would be a path shorter than the shortest path to . That contradicts to Bellman-Ford algorithm’s correctness.

Additionally, the weight modification doesn’t change the shortest paths in the original graph. That is, the path weights in the graph actually change, but the shortest paths before and after the weight modification remain the same. Assume we have a path from vertex to , $P = \{(s, v_1), (v_1, v_2), ..., (v_k, t)\}$ . The weight of before the weight modification is:

weight(P) = weight(s, v_1) + weight(v_1, v_2) + ... + weight(v_k, t)

The new weight of is:

$\boldsymbol{(distance[s] - distance[t])}$ is a constant and doesn’t depend on $\boldsymbol{P}$ , thus if $\boldsymbol{weight(P)}$ was the least before, $\boldsymbol{newWeight(P)}$ would be the least after the weights modification.

3.4. Running Dijkstra’s Algorithm

In the final step, we run Dijkstra’s algorithm for each vertex in the graph with the modified edges. After this step, we’ll have the shortest paths for each vertex pair (u, v) . The shortest path weights are calculated using the modified edge weights.

To calculate the original weights of the shortest paths, we need to parallelly maintain the original weights of the paths during Dijkstra’s algorithm. Alternatively, we can convert the shortest path weights after getting the shortest paths themselves.

4. Johnson’s Algorithm Demonstration on an Example Graph

Let’s pick a directed graph for our example:

directed graph

As we can see, there’re negative-weight edges present. Also, there’re cycles in the graph. Nevertheless, there’re no negative-weight cycles. Now, let’s start the algorithm. First, we add a new vertex and introduce the directed zero-weight edges going out of the added vertex. The added vertex is :

new vertex

It’s time to run the Bellman-Ford algorithm to calculate the shortest paths from to all the graph vertices. We can see the shortest paths within the vertex nodes in red. For example, the shortest path’s weight from to is :

shortest distances

After we’ve calculated the shortest paths from in the previous step, we can modify the edge weights. The original edge weights are left as is, and the new weights are provided in blue within the brackets:

modified edges

Finally, the last step is to run Dijkstra’s algorithm on the graph with the modified edge weights. The resulting pair-wise shortest paths matrix is:

Rendered by QuickLaTeX.com

We can switch back to the original edge weights. The pair-wise shortest paths matrix will then be:

Rendered by QuickLaTeX.com

5. Algorithm Pseudocode

We assume we have functions BELLMANFORD( G, u ) and DIJKSTRA( G, u ) that accept the input graph and the source vertex . They return the shortest paths from to all the remaining vertices in . The pseudocodes for the algorithms can be found in their appropriate discussions: Bellman-Ford and Dijkstra’s algorithms.

The pseudocode for Johnson’s algorithm will then be:

algorithm JohnsonAlgorithm(G):
    // INPUT
    //    G = the graph
    // OUTPUT
    //    M = matrix of pair-wise shortest paths between the vertices of G

    extendedGraph <- G
    s <- a new vertex
    extendedGraph.V <- extendedGraph.V + {s}

    for u in extendedGraph.V:
        if u != s:
            extendedGraph.E <- extendedGraph.E + {(s, u)}

    distance <- BELLMANFORD(extendedGraph, s)

    for (u, v) in G.E:
        G.weight(u, v) <- G.weight(u, v) + distance[u] - distance[v]

    M <- an NxN matrix

    for u in G.V:
        M[u] <- DIJKSTRA(G, u)

    return M

6. The Complexity Analysis

The time complexity of Johnson’s algorithm depends on Bellman-Ford and Dijkstra’s algorithms. Bellman-Ford algorithm runs in O(N * M) . Each invocation of Dijkstra’s algorithm takes O(N * log(N)) time, and we invoke it times, so the overall complexity of the step is O(N^2 * log(N)) .

Thus, Johnson’s algorithm runs in $\boldsymbol{O(N * M + N^2 * log(N))}$ . When is sparse, this is better than O(N^3) running time of the Floyd-Warshall algorithm. Floyd-Warshall algorithm is preferable when is a dense graph where almost all vertex pairs are connected.

The space complexity of Johnson’s algorithm is $\boldsymbol{O(N ^2)}$ as it calculates and returns the pair-wise shortest paths matrix.

7. Conclusion

In this topic, we’ve gone over Johnson’s algorithm. It’s an algorithm to find all-pairs shortest paths in directed and undirected graphs. Johnson’s algorithm uses Bellman-Ford and Dijkstra’s single-source shortest paths algorithms as its subroutines. The algorithm is the best for sparse graphs.

Persistence

REST

Security