Code:
import java.io.*;
class AllPairsShortestPath(Warshalls)
{
public
static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
static
int [][] G;
static
int n;
public
static void main (String[] args) throws IOException
{
System.out.println("\t\t\t\tAll
Pairs Shortest Path");
System.out.print("\nEnter
the number of the vertices: ");
n
= Integer.parseInt(br.readLine());
G
= new int[n+1][n+1];
System.out.print("\nIf
edge between the start and end nodes and its distance (enter -1 to quit) :\n");
for(int
i=1;i<=n;i++)
for(int
j=1;j<=n;j++)
{
if(i
!= j)
G[i][j]=
400000;//+ve infinity
else
G[i][j]
= 0;
}
int
i =0, j=0;
do{
System.out.print("Enter
start node: ");
i
= Integer.parseInt(br.readLine());
if((i<=0)||(i>n))
{
if(i==-1)
break;
System.out.println("Invalid
start node!");
continue;
}
System.out.print("Enter
end node: ");
j
= Integer.parseInt(br.readLine());
if((j<=0)||(j>n))
{
if(j==-1)
break;
System.out.println("Invalid
end node!");
continue;
}
if(j
== i)
{
System.out.println("Start
and end node cant be same!");
continue;
}
System.out.print("Enter
distance between "+i+" and "+j+": ");
G[i][j]
= Integer.parseInt(br.readLine());
}while(
(i !=-1 ) && (j!=-1) );
System.out.println("\n\nSolution
:");
APSP();
}
static
void APSP()
{
int
[][] A = new int[n+1][n+1];
for(int
i=1; i<=n; i++)
for(int
j=1; j<= n; j++)
A[i][j]
= G[i][j];
for(int
k=1; k<=n; k++)
for(int
i=1; i<= n; i++)
for(int
j=1; j<= n; j++)
A[i][j]
= Math.min(A[i][j], A[i][k]+A[k][j]);
for(int
i=1; i<=n; i++)
{
for(int
j=1; j<= n; j++)
{
System.out.print(A[i][j]+"\t");
}
System.out.println();
}
}
}
OUTPUT:
Enter the number of the vertices: 4
If edge between the start and end nodes and its
distance (enter -1 to quit) :
Enter start node: 0
Invalid start node!
Enter start node: 1
Enter end node: 3
Enter distance between 1 and 3: 3
Enter start node: 2
Enter end node: 1
Enter distance between 2 and 1: 2
Enter start node: 4
Enter end node: 1
Enter distance between 4 and 1: 6
Enter start node: 3
Enter end node: 2
Enter distance between 3 and 2: 7
Enter start node: 3
Enter end node: 4
Enter distance between 3 and 4: 1
Enter start node: -1
Solution :
0
10 3 4
2
0 5 6
7
7 0 1
6
16 9 0
Need
the code??
No comments:
Post a Comment