programming-examples/java/Graph_Problems_Algorithms/Johnson.java

package com.jwetherell.algorithms.graph;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.jwetherell.algorithms.data_structures.Graph;

/**
 * Johnson's algorithm is a way to find the shortest paths between all pairs of
 * vertices in a sparse directed graph. It allows some of the edge weights to be
 * negative numbers, but no negative-weight cycles may exist.
 * 
 * Worst case: O(V^2 log V + VE)
 * 
 * https://en.wikipedia.org/wiki/Johnson%27s_algorithm
 * 
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
public class Johnson {

    private Johnson() { }

    public static Map<Graph.Vertex<Integer>, Map<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>>> getAllPairsShortestPaths(Graph<Integer> g) {
        if (g == null)
            throw (new NullPointerException("Graph must be non-NULL."));

        // First, a new node 'connector' is added to the graph, connected by zero-weight edges to each of the other nodes.
        final Graph<Integer> graph = new Graph<Integer>(g);
        final Graph.Vertex<Integer> connector = new Graph.Vertex<Integer>(Integer.MAX_VALUE);

        // Add the connector Vertex to all edges.
        for (Graph.Vertex<Integer> v : graph.getVertices()) {
            final int indexOfV = graph.getVertices().indexOf(v);
            final Graph.Edge<Integer> edge = new Graph.Edge<Integer>(0, connector, graph.getVertices().get(indexOfV));
            connector.addEdge(edge);
            graph.getEdges().add(edge);
        }

        graph.getVertices().add(connector);

        // Second, the Bellman–Ford algorithm is used, starting from the new vertex 'connector', to find for each vertex 'v'
        // the minimum weight h(v) of a path from 'connector' to 'v'. If this step detects a negative cycle, the algorithm is terminated.
        final Map<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> costs = BellmanFord.getShortestPaths(graph, connector);

        // Next the edges of the original graph are re-weighted using the values computed by the Bellman–Ford algorithm: an edge 
        // from u to v, having length w(u,v), is given the new length w(u,v) + h(u) − h(v).
        for (Graph.Edge<Integer> e : graph.getEdges()) {
            final int weight = e.getCost();
            final Graph.Vertex<Integer> u = e.getFromVertex();
            final Graph.Vertex<Integer> v = e.getToVertex();

            // Don't worry about the connector
            if (u.equals(connector) || v.equals(connector)) 
                continue;

            // Adjust the costs
            final int uCost = costs.get(u).getCost();
            final int vCost = costs.get(v).getCost();
            final int newWeight = weight + uCost - vCost;
            e.setCost(newWeight);
        }

        // Finally, 'connector' is removed, and Dijkstra's algorithm is used to find the shortest paths from each node (s) to every 
        // other vertex in the re-weighted graph.
        final int indexOfConnector = graph.getVertices().indexOf(connector);
        graph.getVertices().remove(indexOfConnector);
        for (Graph.Edge<Integer> e : connector.getEdges()) {
            final int indexOfConnectorEdge = graph.getEdges().indexOf(e);
            graph.getEdges().remove(indexOfConnectorEdge);
        }

        final Map<Graph.Vertex<Integer>, Map<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>>> allShortestPaths = new HashMap<Graph.Vertex<Integer>, Map<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>>>();
        for (Graph.Vertex<Integer> v : graph.getVertices()) {
            final Map<Graph.Vertex<Integer>, Graph.CostPathPair<Integer>> costPaths = Dijkstra.getShortestPaths(graph, v);
            final Map<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>> paths = new HashMap<Graph.Vertex<Integer>, List<Graph.Edge<Integer>>>();
            for (Graph.Vertex<Integer> v2 : costPaths.keySet()) {
                final Graph.CostPathPair<Integer> pair = costPaths.get(v2);
                paths.put(v2, pair.getPath());
            }
            allShortestPaths.put(v, paths);
        }
        return allShortestPaths;
    }
}