# Implementation of All Pair Shortest Path Algorithm

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;
System.out.println("Enter the no vertices");
System.out.println("enter no edges");
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));
System.out.println("enter the weight of edge " (i));
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........*/
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.