Floyd warshall algorithm java program. Find the shortest paths between all vertices in a graph using dynamic programming. The matrix and number of vertices as the input(using the scanner), and the shortest path matrix as the output.
Floyd warshall
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 4 images
I have modified the code above. The input to test the method floydWarshal(graph,v) will come from the user (from the console through the scanner). v can not be a final variable because the user will determine the value of v. The double array graph will also be determined and input by the user (from the console through the scanner). I'm having issues getting the input from the user and putting it into the double array. I'm also having issues printing the result of the method, which should be the shortest path graph. Please help
------------------------------------------------------------------------------------
HERE IS THE CODE THAT I HAVE SO FAR
import java.io.*;
import java.util.*;
import java.lang.*;
public class Solution
{
final static int INF = 99999;
public static void shortWarshall(int graph[][],int v)
{
int dist[][] = new int[v][v];
int i, j, k;
/* 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++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one
to the set of intermediate
vertices.
---> Before start of an 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 an 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 vertex k is on the shortest path
// from i to j, then update the value of
// dist[i][j]
if (dist[i][k] + dist[k][j]
< dist[i][j])
dist[i][j]
= dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
// printSolution(dist);
for (int l = 0; l < v; ++l)
{
for (int m = 0; m < v; ++m)
{
if (dist[l][m] == INF)
System.out.print("INF ");
else
System.out.print(dist[l][m] + " ");
}
System.out.println();
}
}
/*public static void printSolution(int dist[][], int v)
{
for (int i = 0; i < v; ++i)
{
for (int j = 0; j < v; ++j)
{
if (dist[i][j] == INF)
System.out.print("INF ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}*/
public static void main(String[] args)
{
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
// Driver's code
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
Scanner scn = new Scanner(System.in);
int v = scn.nextInt();
int c = scn.nextInt();
int r = scn.nextInt();
int graph[][] = new int [c][r];
for(int i=0;i<c;i++)
{
for(int k=0;k<r;k++)
{
graph[i][k]=scn.nextInt();
}
}
// Function call
shortWarshall(graph,v);
}
}
------------------------------------------------------------------
I have also attached the error that I'm getting as a picture
Runtime Error
Error (stderr)
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0 at Solution.shortWarshall(Solution.java:24) at Solution.main(Solution.java:119
by Bartleby Expert
