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?
