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;
        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........*/

Leave a Reply

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