Massive Algorithms: All-pairs shortest paths - Johnson's algorithm for sparse graphs

All-pairs shortest paths - Johnson's algorithm for sparse graphs - GeeksforGeeks

http://www.geeksforgeeks.org/johnsons-algorithm/

Johnson's algorithm: O(V²log V + VE)

Time Complexity: The main steps in algorithm are Bellman Ford Algorithm called once and Dijkstra called V times. Time complexity of Bellman Ford is O(VE) and time complexity of Dijkstra is O(VLogV). So overall time complexity is O(V²log V + VE).
The time complexity of Johnson's algorithm becomes same as Floyd Warshell when the graphs is complete (For a complete graph E = O(V²). But for sparse graphs, the algorithm performs much better than Floyd Warshell.

If we apply Dijkstra’s Single Source shortest path algorithm for every vertex, considering every vertex as source, we can find all pair shortest paths in O(V*VLogV) time. So using Dijkstra’s single source shortest path seems to be a better option than Floyd Warshell, but the problem with Dijkstra’s algorithm is, it doesn’t work for negative weight edge.
The idea of Johnson’s algorithm is to re-weight all edges and make them all positive, then apply Dijkstra’s algorithm for every vertex.

Johnson's algorithm finds shortest paths between all pairs by using both Dijkstra's algorithm and the Bellman-Ford algorithm as subroutines.

How to transform a given graph to a graph with all non-negative weight edges?

The idea of Johnson’s algorithm is to assign a weight to every vertex. Let the weight assigned to vertex u be h[u]. We reweight edges using vertex weights. For example, for an edge (u, v) of weight w(u, v), the new weight becomes w(u, v) + h[u] – h[v]. The great thing about this reweighting is, all set of paths between any two vertices are increased by same amount and all negative weights become non-negative. Consider any path between two vertices s and t, weight of every path is increased by h[s] – h[t], all h[] values of vertices on path from s to t cancel each other.

How do we calculate h[] values? Bellman-Ford algorithm is used for this purpose. Following is the complete algorithm. A new vertex is added to the graph and connected to all existing vertices. The shortest distance values from new vertex to all existing vertices are h[] values.

How does the transformation ensure nonnegative weight edges?The following property is always true about h[] values as they are shortest distances. h[v] <= h[u] + w(u, v)

The property simply means, shortest distance from s to v must be smaller than or equal to shortest distance from s to u plus weight of edge (u, v). The new weights are w(u, v) + h[u] - h[v]. The value of the new weights must be greater than or equal to zero because of the inequality "h[v] <= h[u] + w(u, v)".

http://joonki-jeong.blogspot.com/2013/01/johnsons-algorithm.html

Dijkstra's algorithm and the Bellman-Ford algorithm finds shortest paths from the single source vertex to others. Dijkstra's algorithm runs in O(n*lg n) to compute shortest paths while the Bellman-Ford runs in O(n*m), where n is the number of vertices and m is the number of edges.

However, Dijkstra's algorithm has one shortcoming, which is the constraint that the input graph must not have negative cost edges. On the other hand, the Bellman-Ford allows the input graph to have negative cost edges, but no negative cost cycles.

To overcome the constraints of the two single source shortest path algorithms, Johnson's algorithm uses the technique of re-weighting. Johnson's algorithm follows the steps below.

Given a weighted, directed graph G=(V,E) with weight function w : E -> R. Weights might or might not be negative.

Form G' by adding a new vertex s and a new edge (s,v) with weight 0 for each v in V.
Run Bellman-Ford algorithm on G' with source vertex s
(If B-F algorithm detects a negative cost cycle in G', halt and report this).
For each v in G, let P[v] be the length of a shortest path from s to v in G'. For each edge e = (u,v) in G, define 'new weight' = 'old weight' + P[u] - P[v].
For each vertex u of G:
Run Dijkstra's algorithm in G with edge costs {new weights}, with source vertex u to compute the shortest path distance d'(u,v) for each v in G.
For each pair (u,v) in G, return the shortest path distance d(u,v) = d'(u,v) - P[u] + P[v].

(a).

A new vertex is added to G with weight 0 to other vertices(Step 1). Then, run the Bellman-Ford algorithm on G(Step 2).

(b).

For each edge in G', re-weight the edge weight(Step 3). Please note that all edge weights are non-negative.

Remove newly added vertex and run Dijkstra's algorithm for each vertex v in G(Step 4).

You will end up having the all-pair shortest paths sequences(vertices) for now, but one more step to compute the real value of the shortest paths. By step 5, you will undo re-weighting and have the original weights of shortest paths between all pairs of vertices.

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 BELLMAN-FORD (G', w, s) == FALSE:
print "the input graph contains a negative-weight cycle"
else
for each vertex v in G'.V:
set h(v) to the value of q(s,v) computed by the Bellman-Ford algorithm.
for each edge (u,v) in G'.E:
w'(u,v) = w(u,v) + h(u) - h(v)
let D = d(u,v) be a new n x n matrix
for each vertex u in G.V:
run DIJKSTRA (G, w', u) to compute q'(u,v) for all v in G.V
for each vertex v in G.V:
d(u,v) = q'(u,v) + h(v) - h(u)
return D

Cpp complete code: https://gist.github.com/ashleyholman/6793360
http://www.keithschwarz.com/interesting/code/johnson/Johnson.java.html
    private static final Object SOURCE_NODE = new Object();
    public static <T> DirectedGraph<T> shortestPaths(DirectedGraph<T> graph) {
        /* Construct the augmented graph G' that will be fed into the Bellman-
         * Ford step by copying the graph and adding an extra node.  Because
         * the source node is of type Object (because we can't necessarily
         * create an element of type T that isn't already in the graph), this
         * graph will store plain old Objects.
         */
        DirectedGraph<Object> augmentedGraph = constructAugmentedGraph(graph);

        /* Compute the single-source shortest path from the source node to
         * each other node in the graph to get the potential function h.
         */
        Map<Object, Double> potential = BellmanFord.shortestPaths(augmentedGraph, SOURCE_NODE);

        /* Now, reweight the edges of the input graph by adjusting edge
         * weights based on the potential.
         */
        DirectedGraph<T> reweightedGraph = reweightGraph(graph, potential);

        /* Our return value is a graph with the all-pairs shortest paths
         * values for edges.  We'll begin by initializing it so that it has a
         * copy of each node in the source graph.
         */
        DirectedGraph<T> result = new DirectedGraph<T>();
        for (T node: graph)
            result.addNode(node);

        /* Now, run Dijkstra's algorithm over every node in the updated graph
         * to get the transformed shortest path costs.
         */
        for (T node: graph) {
            Map<T, Double> costs = Dijkstra.shortestPaths(reweightedGraph, node);

            /* We now have the shortest path costs from this node to all other
             * nodes, but the costs are using the new edges rather than the
             * old.  In particular, we have that
             *
             *                  C'(u, v) = C(u, v) + h(u) - h(v)
             *
             * When recording these costs in the new graph, we'll therefore
             * add in h(v) - h(u).
             */
            for (Map.Entry<T, Double> path: costs.entrySet())
                result.addEdge(node, path.getKey(),
                               path.getValue() + potential.get(path.getKey()) - potential.get(node));
        }

        /* Hand back the resulting graph. */
        return result;
    }
    private static <T> DirectedGraph<Object> constructAugmentedGraph(DirectedGraph<T> graph) {
        DirectedGraph<Object> result = new DirectedGraph<Object>();

        /* Copy over the nodes. */
        for (Object node: graph)
            result.addNode(node);

        /* Copy over the edges. */
        for (T node: graph)
            for (Map.Entry<T, Double> edge: graph.edgesFrom(node).entrySet())
                result.addEdge(node, edge.getKey(), edge.getValue());

        /* Add the new node to the graph. */
        result.addNode(SOURCE_NODE);

        /* Connect it to each other node with an edge of cost zero. */
        for (Object node: graph)
            result.addEdge(SOURCE_NODE, node, 0.0);

        return result;
    }urn A reweighted version of the graph.
     */
    private static <T> DirectedGraph<T> reweightGraph(DirectedGraph<T> graph,
                                                      Map<Object, Double> potential) {
        /* Begin by copying over all the nodes from the old graph. */
        DirectedGraph<T> result = new DirectedGraph<T>();
        for (T node: graph)
            result.addNode(node);

        /* Now, copy over the edge with new weights; in particular, by using
         * l'(u, v) = l(u, v) - l(v) + l(u).
         */
        for (T node: graph)
            for (Map.Entry<T, Double> edge: graph.edgesFrom(node).entrySet())
                result.addEdge(node, edge.getKey(),
                               edge.getValue() + potential.get(node) - potential.get(edge.getKey()));

        return result;
    }
Read full article from Johnson's algorithm for All-pairs shortest paths - GeeksforGeeks

All-pairs shortest paths - Johnson's algorithm for sparse graphs - GeeksforGeeks

Labels

Popular Posts