import java.io.*;
import java.util.*;
class graph
{
int g[][],v,e,i,j,k;
void creatgraph()
{
Scanner s=new Scanner(System.in);
int a,b,w;
System.out.println("Enter no of vertices");
v=s.nextInt();
System.out.println("Enter no of edges");
e=s.nextInt();
g=new int[v+1][v+1];
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
g[i][j]=32767;
for(int i=1;i<=v;i++)
g[i][i]=0;
for(int i=1;i<=e;i++)
{
System.out.println("Enter edge information:");
a=s.nextInt();
b=s.nextInt();
System.out.println("Enter weight of edge:");
w=s.nextInt();
g[a][b]=w;
}
}
void allpair()
{
for(int k=1;k<=v;k++)
for(int i=0;i<=v;i++)
for(int j=0;j<=v;j++)
g[i][j]=Math.min(g[i][j],g[i][k]+g[k][j]);
System.out.println("");
System.out.println("The shortest path for all vertices is given by a matrix");
System.out.println("");
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
{
System.out.print(g[i][j]+" ");
}
System.out.println();
}
}
}
class allpairshortest
{
public static void main(String args[])
{
graph g=new graph();
g.creatgraph();
g.allpair();
}
}
OUTPUT:
Enter no of vertices
4
Enter no of edges
5
Enter edge information:
1
2
Enter weight of edge:
7
Enter edge information:
2
3
Enter weight of edge:
8
Enter edge information:
3
4
Enter weight of edge:
9
Enter edge information:
4
1
Enter weight of edge:
10
Enter edge information:
1
3
Enter weight of edge:
11
The shortest path for all vertices is given by a matrix
0 7 11 20
27 0 8 17
19 26 0 9
10 17 21 0
Press any key to continue...
No comments:
Post a Comment