trjhtr

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] + "tt");
 
 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++) 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++) 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?