All pair shortest path algorithm is used to find shortest distance between each pair of vertices.
//Implementation of ALL PAIR SHORTEST PATH algorithm
import java.io.*;
class Graph {
int g[][];
int v, e;
void Creategraph() throws IOException {
int a, b, w;
InputStreamReader cin = new InputStreamReader(System.in);
BufferedReader obj = new BufferedReader(cin);
System.out.println("Enter the no vertices");
v = Integer.parseInt(obj.readLine());
System.out.println("enter no edges");
e = Integer.parseInt(obj.readLine());
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 end vertices of edge " + (i));
a = Integer.parseInt(obj.readLine());
b = Integer.parseInt(obj.readLine());
System.out.println("enter the weight of edge " (i));
w = Integer.parseInt(obj.readLine());
g[a][b] = g[b][a] = w;
}
}
void allpair() {
for (int k = 1; k <= v; k++) {
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++)
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
System.out.println("shortest distance path is");
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++)
System.out.println(i + " - " + j + "=" + g[i][j]);
}
}
}
public class Allpair {
public static void main(String args[]) throws IOException {
Graph g = new Graph();
g.Creategraph();
g.allpair();
}
}
/*OUTPUT
Enter the no vertices 4
enter no edges 5
Enter the two vertices between which edge is present 1 2
enter the weight of edge 2
Enter the two vertices between which edge is present 1 3
enter the weight of edge 5
Enter the two vertices between which edge is present 2 4
enter the weight of edge 3
Enter the two vertices between which edge is present 3 4
enter the weight of edge 6
Enter the two vertices between which edge is present 1 4
enter the weight of edge 4
shortest distance path is
1 - 1=0
1 - 2=2
1 - 3=5
1 - 4=4
2 - 1=2
2 - 2=0
2 - 3=7
2 - 4=3
3 - 1=5
3 - 2=7
3 - 3=0
3 - 4=6
4 - 1=4
4 - 2=3
4 - 3=6
4 - 4=0
Process Exit........*/