Implementation and Analysis of Shortest Path Algorithms in Java

This Java code implements the Floyd-Warshall algorithm to find the shortest paths between all pairs of vertices in a weighted graph. The code initializes a distance matrix with the graph's edge weights and then iteratively updates these distances, considering each vertex as an intermediate node. It also calculates the hop count (number of edges) and reconstructs the shortest paths. Furthermore, the code calculates Load, G function, and final path, and prints the predicted distance, hop count, and paths. The code defines a `ShortestPath` class containing the `floydWarshall` method, which computes the shortest paths, and the `LoadandGFunction` method, which calculates Load and G values. The `main` method demonstrates the usage of the algorithm with a sample graph and prints the results. The implementation includes handling of infinite distances and path reconstruction. The code is well-commented and provides a clear understanding of the algorithm's steps.

import java.awt.*;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.List;
class ShortestPath {
final static int INF = 99999, V = 6;
int i, j, k;
String[] str = null;
DecimalFormat df = new DecimalFormat("#.##");
List floydWarshall(double graph[][]) {
double hop[][] = new double[V][V];
double distance[][] = new double[V][V];
String path[][] = new String[V][V];
// String path[][] = {
// {"1","1","1","1","1","1"},
// {1,"1","1","1","1","1"},
// {1,1,0,1,1,1},
// {1,1,1,0,1,1},
// {1,1,1,1,0,1},
// {1,1,1,1,1,0}
//
// };
/* Initialize the solution matrix same as input graph matrix.
Or we can say the initial values of shortest distances
are based on shortest paths considering no intermediate
vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++){
distance[i][j] = graph[i][j];
if(i != j){
hop[i][j]=1;
path[i][j] = "(" + (i + 1) + "," + (j + 1) + ")";
}else path [i][j]= ""+(j+1)+"";
}
/* Add all vertices one by one to the set of intermediate
vertices.
---> Before start of a iteration, we have shortest
distances between all pairs of vertices such that
the shortest distances consider only the vertices in
set {0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of a iteration, vertex no. k is added
to the set of intermediate vertices and the set

becomes {0, 1, 2, .. k} */
for (k = 0; k < V; k++) {
// Pick all vertices as source one by one
for (i = 0; i < V; i++) {
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++) {
if (path[i][j] == null && i != j) {
path[i][j] = "(" + (i + 1) + "," + (j + 1) + ")";
//hop[i][j]=1;
//path[i][j] = "("+(i+1)+","+(j+1)+")";
}
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (distance[i][k] + distance[k][j] < distance[i][j]) {
distance[i][j] = distance[i][k] + distance[k][j];
//hop[i][j]++;
// if (path[i][j]!= null)
path[i][j] = path[i][k] + path[k][j];
hop[i][j] = hop[i][k] + hop[k][j];
/*if (graph[i][k]!= 99999) Loud[i][k]=Loud[i][k]+Flow[i][j];
if (graph[k][j]!= 99999) Loud[k][j]=Loud[k][j]+Flow[i][j];*/
//if( graph[i][j]!= 99999) Loud[i][k]=Flow[i][j];
//path[i][j] = "("+(i+1)+","+(k+1)+","+(j+1)+")"+path[i][j];
// else path[i][j] = "("+(i+1)+","+(k+1)+","+(j+1)+")";
} else {
if (hop[i][j] == 0 && i != j) {
//hop[i][j]=1;
//path[i][j] = "("+(i+1)+","+(j+1)+")";
}
}
}
}
}
List<Object> list = new ArrayList<Object>();
for ( i= 0; i < V; i++) {
for (j = 0; j < V; j++) {
distance[i][j] = (double)Math.round( distance[i][j] * 1000d) / 1000d ;
}
}
list.add(distance);
list.add(hop);
list.add(path);
return list;
}
List LoadandGFunction(double graph[][], double Flow[][],double[]
[]Capacity,String[][] path) {

double Load[][] = new double[V][V];
double G[][]= new double[V][V];
double final_path[][] = new double[V][V];
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (graph[i][j] == INF) Load[i][j] = INF;
else if (i == j) {
Load[i][j] = 0;
} else if (!path[i][j].equals("(" + (i + 1) + "," + (j + 1) + ")")) {
//System.out.print(i + 1 + "\t" + (j + 1) + "\t" + path[i][j] + "\n");
Load[i][j] = 0;
} else if (path[i][j].equals("(" + (i + 1) + "," + (j + 1) + ")")) {
for (k = 0; k < V; k++) {
for (int l = 0; l < V; l++) {
if (path[k][l] != null)
if (path[k][l].contains(path[i][j])) {
//System.out.print("i new: " + i + " j new : " + j + '\t' + "k
new: " + k + " l new: " + l + '\n');
Load[i][j] = Load[i][j] + Flow[k][l];
//System.out.print("i new: "+ i + " j new : " + j + '\t' + "k
new: "+ k + " l new: " + l + '\n');
}
}
}
}
}
}
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (Load[i][j] <= Capacity[i][j]) {
if (graph[i][j] == INF)
G[i][j] = INF;
else
G[i][j] = ((Capacity[i][j] + 1) / (Capacity[i][j] + 1 - Load[i][j])) *
graph[i][j];
} else
G[i][j] = INF;
//System.out.print("i "+ " j " + G[i][j]+'\n');
}
}
for (i = 0; i < V; i++) {
for ( j = 0; j < V; j++) {
if ( i!=j) {
str = path[i][j].replaceAll("[^-?0-9]+", " ").split(" ");

ArrayList<Integer> integerList = new ArrayList<Integer>();
float value = 0;
for (k = 1;k < str.length;k++){
//System.out.println(str[k]);
integerList.add(Integer.parseInt(str[k]));
//System.out.println(str[k]);
//str = ArrayUtils.removeElement(str, 0);
}
//System.out.println(integerList.size()+'\n');
//System.out.println('\n');
//System.out.println(integerList);
for (k = integerList.size()-1;k > 0;k--){
//System.out.print("k-1 : "+integerList.get(k-1)+" k:
"+integerList.get(k)+'\n');
value += G[integerList.get(k-1)-1][integerList.get(k)-1];
}
final_path[i][j] = value;
//System.out.println(value);
}
else
final_path [i][j] = 0;
}
}
//printSolution(final_path);
//ArrayList<2DArray> myList = new ArrayList<2DArray>;
ArrayList<double[][]> myList = new ArrayList<double[][]>();
for ( i= 0; i < V; i++) {
for (j = 0; j < V; j++) {
Load[i][j] = (double)Math.round( Load[i][j] * 1000d) / 1000d ;
G[i][j] = (double)Math.round( G[i][j] * 1000d) / 1000d ;
final_path[i][j] = (double)Math.round( final_path[i][j] * 1000d) /
1000d ;
}
}
myList.add(Load);
myList.add(G);
myList.add(final_path);
//return (new double[](Load, G));
return myList;
}
void printSolution(double dist[][])
{
System.out.println("Following matrix shows the shortest "+
"distances between every pair of vertices");
for (int i=0; i<V; ++i)
{
for (int j=0; j<V; ++j)
{

if (dist[i][j]==INF)
System.out.print("na\t");
else
System.out.print(dist[i][j]+"\t");
}
System.out.println();
}
}
void printSolutionS(String dist[][])
{
System.out.println("Following matrix shows the shortest "+
"Path");
for (int i=0; i<V; ++i)
{
for (int j=0; j<V; ++j)
{
if (dist[i][j]=="INF")
System.out.print("INF ");
else {String format = "%-40s%s%n";//"%-40s%s%n" "%1$13s"
System.out.printf(format, ""+(i+1)+"=>"+(j+1)+ " : "+dist[i][j], "\t");}
// System.out.print(dist[i][j]+"\t");
}
System.out.println();
}
}
// Driver program to test above function
public static void main (String[] args)
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
// int graph[][] = { {0, 5, INF, 10},
// {INF, 0, 3, INF},
// {INF, INF, 0, 1},
// {INF, INF, INF, 0}
// };
//
double graph[][] = {
{0, 7, INF, 7,INF,9},
{INF, 0, 5, INF,10,3},
{9, 10, 0, 8,4,6},
{9,4,2,0,INF,INF},
{3, 5, 10, 10,0,INF},
{INF,5, 8, 10, INF,0}
};
double[][] Flow = {
{0, 9, 11, 12, 8, 12},

{18, 0, 15, 10, 17, 18},
{17, 18, 0, 14, 10, 10},
{17, 8, 10, 0, 17, 18},
{15, 9, 12, 14, 0, 16},
{18, 16, 15, 8, 9, 0}
};
// double[][] Flow = {
// {0,1,1,1,1,1},
// {1,0,1,1,1,1},
// {1,1,0,1,1,1},
// {1,1,1,0,1,1},
// {1,1,1,1,0,1},
// {1,1,1,1,1,0}
//
// };
double[][] Capacity = {
{0, 13, INF, 33, INF, 20},
{INF, 0, 67, INF, 5, 55},
{5, 5, 0, 32, 134, 17},
{23, 34, 55, 0, INF, INF},
{68, 47, 20, 14, 0, INF},
{INF, 16, 44, 16, INF, 0}
};
ShortestPath a = new ShortestPath();
// Print the solution
List<Object> mlist = a.floydWarshall(graph);
//List<Object> mlist = a.floydWarshall(grapha);
System.out.print("Predicted Distance: ");
a.printSolution( (double[][])mlist.get(0));
System.out.print("\nHop Count: ");
a.printSolution( (double[][])mlist.get(1));
System.out.print("\nPath ");
a.printSolutionS((String [] []) mlist.get(2));
//a.printSolution( (double[][])mlist.get(0));
//String[] [] path = (String [] []) mlist.get(2);
//printSolution(dist);
//printSolution(hop);
//printSolutionS(path);
List b = a.LoadandGFunction(graph,Flow,Capacity,(String [] [])mlist.get(2));
System.out.print("\nload: ");
a.printSolution((double[][])b.get(0));
System.out.print("\nCongested Path: ");
a.printSolution((double[][])b.get(1));
System.out.print("\nFinal Path: ");
a.printSolution((double[][])b.get(2));
/*List<Object> newlist = a.floydWarshall((double[][]) b.get(1));
System.out.print("\nActual Distance: ");

a.printSolution( (double[][])newlist.get(0));
System.out.print("\nHop Count: ");
a.printSolution( (double[][])newlist.get(1));
System.out.print("\nPath ");
a.printSolutionS((String [] []) newlist.get(2));*/
}
}