Optimizing Graph Algorithms for Floyd Warshall and Johnson Algorithm

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.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;
}

//function that takes in input an adjacency matrix and produces and adjacency list

for(int i=0; i<n; i++){
}

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

}

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];

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++;
}
}

// 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();
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;
}
}

//function that takes in input an adjacency matrix and produces and adjacency list

for(int i=0; i<n; i++){
}

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

}

double d[][] = new double[n][n];

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

return d;
}

for(int i=0; i<n; i++){
}
}

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++) {
}

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
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()];
}
}
}

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;

for (int i = 0; i < n - 1; i++) {
//relax all the edges
for(int j=0; j<n; 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++) {
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;
}

for(int i=0; i<n; i++){
}

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

PathDistance bellmanfordresult;
PathDistance dijkstraresult;

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++){
edge.nodeweight = edge.nodeweight + h[i] - h[edge.nodeindex];
}
}

// now run dijkstra for each vertex
for (int i = 0; i < n; 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()];
`