Shortest Path Algorithm: Floyd-Warshall Implementation in Java
VerifiedAdded on  2019/09/13
|7
|3099
|419
Report
AI Summary
The assignment is about implementing the Floyd Warshall algorithm to find the shortest path and hop count in a weighted graph, then using this information to calculate the load on each link and identify congested paths. The program takes as input the weighted graph, flow values, capacity values, and an initial path. It outputs the predicted distance, hop count, and actual path taken by the traffic, as well as the load on each link and congested paths.
Contribute Materials
Your contribution can guide someone’s learning journey. Share your
documents today.
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
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
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
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) {
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(" ");
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)
{
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)
{
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
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},
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: ");
{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));*/
}
}
System.out.print("\nHop Count: ");
a.printSolution( (double[][])newlist.get(1));
System.out.print("\nPath ");
a.printSolutionS((String [] []) newlist.get(2));*/
}
}
1 out of 7
Your All-in-One AI-Powered Toolkit for Academic Success.
 +13062052269
info@desklib.com
Available 24*7 on WhatsApp / Email
Unlock your academic potential
© 2024  |  Zucol Services PVT LTD  |  All rights reserved.