4
\$\begingroup\$

I am trying to implement and compare Floyd Warshall and Johnson Algorithm(for Sparse Graphs). I have written the following code which produces correct output values for the all pair shortest paths. However theoretically, Johnson's Algorithm should perform better than Floyd Warshall on sparse graphs. However, the run times suggest otherwise. I have used some random graphs for test purposes. Generating random number of vertices say n and an edge number between 0 and `n.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Random;


public class ShortestPaths {

    public static void printArray(double arr[][], int m, int n) {
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < n; y++) {
                System.out.print(arr[x][y] + "\t\t");
            }
            System.out.println();
        }
    }

    public static int generateRandomBetween(int low, int high) {
        Random r = new Random();
        int result = r.nextInt(high - low) + low;
        return result;
    }

    public static double mean(double[] p) {
        double sum = 0;  // sum of all the elements
        for (int i=0; i<p.length; i++) {
            sum += p[i];
        }
        return sum / p.length;
    }

    public static ArrayList<LinkedList<Integer>> adjacencyList(double g[][], int n){
        //function that takes in input an adjacency matrix and produces and adjacency list
        ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>();

        //add the vertices
        for(int i=0; i<n; i++){
            adj_list.add(new LinkedList<Integer>());
        }

        //now add the edges
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i!=j || g[i][j] != Double.POSITIVE_INFINITY){
                    adj_list.get(i).add(j);
                }
            }
        }

        return adj_list;
    }

    public void generateGraphs() {
        // n is the number of vertices
        // m is the number of edges

        // m is $m=O(n)$

        int n = 0;
        int m = 0;

        Random r = new Random();

        long startTime = 0;
        long endTime = 0;

        double timeFloyd[] = new double[100];
        double timeJohnson[] = new double[100];

        //ArrayList<LinkedList<Integer>> adj_list;

        for (int i = 0; i < 10; i++) {
            // System.out.println(n + "\t" + m);

            n = ShortestPaths.generateRandomBetween(2, 50); // (1 2) generates 1
                                                            // --- generates
                                                            // inclusive lower
                                                            // value, and higher
                                                            // value - 1
            m = ShortestPaths.generateRandomBetween(0, n);

            // for each n-m pair generate 100 graphs

            for (int k = 0; k < 10; k++) {
                double g[][] = new double[n][n];

                for (int x = 0; x < n; x++) {
                    for (int y = 0; y < n; y++) {
                        if (x != y)
                            g[x][y] = Double.POSITIVE_INFINITY;
                    }
                }

                int count = 0; //counter for number of edges

                while(count != m) {
                    // generate a random edge with a random weight
                    // generate m such edges
                    int from = ShortestPaths.generateRandomBetween(0, n);
                    int to = ShortestPaths.generateRandomBetween(0, n);
                    double weight = r.nextDouble();
                    if (from != to){
                        g[from][to] = weight;
                        count++;
                    }
                }

                // generate adjacency list
                //adj_list = ShortestPaths.adjacencyList(g, n);

                // System.out.println();
                System.out.println("Graph Number : " + i + "\t " + n + "\t " + m);
                startTime = System.nanoTime();
                floydWarshall(g, n, m);
                endTime = System.nanoTime();

                timeFloyd[k] = endTime - startTime;

                startTime = System.nanoTime();
                johnson(ShortestPaths.adjacencyListWeight(g, n), n, m);
                endTime = System.nanoTime();

                timeJohnson[k] = endTime - startTime;

            }

            System.out.println("Time for Floyd Warshall : " + ShortestPaths.mean(timeFloyd));
            System.out.println("Time for Johnson : " + ShortestPaths.mean(timeJohnson));
        }
    }

    static class Vertex implements Comparable<Vertex> {
        private int vertexid;
        private double distance;

        public Vertex(int vertexid, Double distance) {
            this.vertexid = vertexid;
            this.distance = distance;
        }

        public int getVertexid() {
            return vertexid;
        }

        public Double getDistance() {
            return distance;
        }

        public int compareTo(Vertex other) {
            return this.getDistance().compareTo(other.getDistance());
        }

        public boolean equals(Object o) {
            if (o instanceof Vertex) {
                Vertex v = (Vertex) o;
                return vertexid == v.vertexid && distance == v.distance;
            }
            return false;
        }
    }

    static class PathDistance {
        boolean containsNegativeCycle;
        double distance[];

        public PathDistance(int n) {
            containsNegativeCycle = false;
            distance = new double[n];
        }
    }

    static class Pair{
        int nodeindex;
        double nodeweight;

        Pair(int nodeindex, double nodeweight){
            this.nodeindex = nodeindex;
            this.nodeweight = nodeweight;
        }
    }

    public static ArrayList<LinkedList<Pair>> adjacencyListWeight(double g[][], int n){
        //function that takes in input an adjacency matrix and produces and adjacency list
        ArrayList<LinkedList<Pair>> adj_list = new ArrayList<LinkedList<Pair>>();

        //add the vertices
        for(int i=0; i<n; i++){
            adj_list.add(new LinkedList<Pair>());
        }

        //now add the edges
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i!=j || g[i][j] != Double.POSITIVE_INFINITY){
                    adj_list.get(i).add(new Pair(j, g[i][j]));
                }
            }
        }

        return adj_list;
    }

    public static double[][] adjacencyMatrix(ArrayList<LinkedList<Pair>> adjacenecyList, int n){
        double d[][] = new double[n][n];

        for(int i=0; i<n; i++){
            for(Pair l : adjacenecyList.get(i)){
                d[i][l.nodeindex] = l.nodeweight;
            }
        }

        return d;
    }

    public static ArrayList<LinkedList<Integer>>  adjacencyConversion(ArrayList<LinkedList<Pair>> adjacenecyList, int n){
        ArrayList<LinkedList<Integer>> d = new ArrayList<LinkedList<Integer>>();


        for(int i=0; i<n; i++){
            d.add(new LinkedList<Integer>());
            for(Pair l : adjacenecyList.get(i)){
                d.get(i).add(l.nodeindex);
            }
        }

        return d;
    }

    public static PathDistance dijkstra(ArrayList<LinkedList<Integer>> adj_list, double g[][], int n, int m, int source) {
        // g is the adjacency matrix
        // n is the number of nodes
        // m is the number of edges

        // initialize shortest path

        double d[] = new double[n];

        PathDistance dijkstraResult = new PathDistance(n);
        dijkstraResult.containsNegativeCycle = false;

        for (int i = 0; i < n; i++) {
            d[i] = Double.POSITIVE_INFINITY;
        }
        d[source] = 0;

        HashMap<Integer, Double> s = new HashMap<Integer, Double>();
        PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();

        // initialize q
        for (int i = 0; i < n; i++) {
            q.add(new Vertex(i, d[i]));
        }

        Vertex u;

        while (!q.isEmpty()) {
            u = q.remove();
            // System.out.println(u.getVertexid() + "\t" + u.getDistance());
            s.put(u.getVertexid(), u.getDistance());

            //check all vertices which are adjacent to u
            for(Integer l : adj_list.get(u.getVertexid())){
                if (u.getDistance().doubleValue() + g[u.getVertexid()][l.intValue()] < d[l.intValue()] && s.containsKey(l.intValue()) == false) {
                    q.remove(new Vertex(l.intValue(), d[l.intValue()]));
                    d[l.intValue()] = u.getDistance().doubleValue() + g[u.getVertexid()][l.intValue()];
                    q.add(new Vertex(l.intValue(), d[l.intValue()]));
                }
            }
        }

        for (int i = 0; i < n; i++) {
            dijkstraResult.distance[i] = s.get(i);
        }

        return dijkstraResult;
    }

    public static PathDistance bellmanford(ArrayList<LinkedList<Integer>> adj_list, double g[][], int n, int m, int source) {
        // g is the adjacency matrix
        // n is the number of nodes
        // m is the number of edges

        // initialize shortest path

        PathDistance result = new PathDistance(n);

        double d[] = new double[n];

        for (int i = 0; i < n; i++) {
            d[i] = Double.POSITIVE_INFINITY;
        }
        d[source] = 0;

        LinkedList<Integer> l;

        for (int i = 0; i < n - 1; i++) {
            //relax all the edges
            for(int j=0; j<n; j++){
                l = adj_list.get(j);
                for(Integer edge : l){
                    if ( d[j] + g[j][edge] < d[edge]){
                        d[edge] = d[j] + g[j][edge];
                    }
                }
            }
        }
        // do one more round of relaxation
        // if we can relax once more, a negative cycle exists
        for (int j = 0; j < n; j++) {
            l = adj_list.get(j);
            for(Integer edge:l){
                if ((d[j] + g[j][edge]) < d[edge])
                    result.containsNegativeCycle = true;
            }
        }

        result.containsNegativeCycle = false;
        for (int i = 0; i < n; i++) {
            result.distance[i] = d[i];
        }

        return result;
    }

    public static double[][] johnson(ArrayList<LinkedList<Pair>> adj_list, int n, int m) {

        LinkedList<Pair> p = new LinkedList<Pair>();

        for(int i=0; i<n; i++){
            p.add(new Pair(i, 0));
        }

        adj_list.add(p);

        double result[][] = new double[n][n];
        double h[] = new double[n + 1];

        PathDistance bellmanfordresult;
        PathDistance dijkstraresult;

        bellmanfordresult = bellmanford(ShortestPaths.adjacencyConversion(adj_list, n+1), ShortestPaths.adjacencyMatrix(adj_list, n+1), n + 1, m, n);

        if (bellmanfordresult.containsNegativeCycle == true) {
            System.out.println("Negative Weight Cycle");
        } else {
            // set h[v] to be the vale computed by bellman ford
            for (int i = 0; i < n + 1; i++) {
                h[i] = bellmanfordresult.distance[i];
            }

            //now reweight all the edges

            for(int i=0; i<n; i++){
                for(Pair edge :adj_list.get(i)){
                    edge.nodeweight = edge.nodeweight + h[i] - h[edge.nodeindex];
                }
            }

            adj_list.remove(n);

            ArrayList<LinkedList<Integer>> adjList = ShortestPaths.adjacencyConversion(adj_list, n);
            double adjMatrix[][] = ShortestPaths.adjacencyMatrix(adj_list, n);
            // now run dijkstra for each vertex
            for (int i = 0; i < n; i++) {
                dijkstraresult = dijkstra(adjList, adjMatrix, n, m, i);
                for (int j = 0; j < n; j++) {
                    result[i][j] = dijkstraresult.distance[j] + h[i] - h[j];
                }
            }
        }

        //System.out.println("Johnson Algorithm");
        //ShortestPaths.printArray(result, n, n);
        return result;
    }

    public static void floydWarshall(double g[][], int n, int m) {
        double[][] distances;
        distances = Arrays.copyOf(g, n);

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
                }
            }

            if (distances[k][k] < 0.0) {
                System.out.println("Has Negative Cycle");
            }
        }

        //System.out.println("Floyd Warshall Algorithm");
        //ShortestPaths.printArray(distances, n, n);
    }

    public static void main(String[] args) {
        ShortestPaths f = new ShortestPaths();
        f.generateGraphs();
    }
}

I have my doubts on how efficient the following part of the code is :

                        q.remove(new Vertex(l.intValue(), d[l.intValue()]));
                        d[l.intValue()] = u.getDistance().doubleValue() + g[u.getVertexid()][l.intValue()];
                        q.add(new Vertex(l.intValue(), d[l.intValue()]));

Except for using a binomial or a fibonacci heap, are there any other optimizations that can be made to this code?

\$\endgroup\$
  • \$\begingroup\$ Have you tried swapping the order to run them? JIT compiler might optimise some things in between. What kind of timings are we talking about here? If it's only miliseconds it might also just be your PC running something else for a couple of miliseconds interupting one of the algorithms for example. \$\endgroup\$ – Imus Apr 13 '18 at 7:11
  • \$\begingroup\$ Yes it's in milliseconds only for small graphs I haven't tested with swapping the orders. I'll try that out. But for large graphs it's not in milliseconds. \$\endgroup\$ – kauray Apr 13 '18 at 7:45
  • \$\begingroup\$ @Imus Swapping the orders does not work. How do i measure the CPU clock time then if the PC is running something else? \$\endgroup\$ – kauray Apr 13 '18 at 16:53
  • \$\begingroup\$ benchmarking is a tricky thing \$\endgroup\$ – Imus Apr 20 '18 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.