In this post, we’ll walk through how to implement the All Pair Shortest Path algorithm in Java — a classic solution to find the shortest distances between every pair of vertices in a weighted graph.

What is the All Pair Shortest Path Problem?

The All Pair Shortest Path (APSP) problem involves finding the shortest distance between every possible pair of vertices in a graph. It’s commonly solved using Floyd-Warshall’s Algorithm, a dynamic programming approach that repeatedly updates the shortest distances between pairs of vertices by considering intermediate vertices.

How the Floyd-Warshall Algorithm Works

The core idea is to iteratively improve the estimate of the shortest path between any two vertices (i, j) by considering whether a path through a third vertex k would be shorter.

Here’s a breakdown:

1. Initialize the adjacency matrix:
   • Set the distance between every vertex to infinity (or a large value like 32767 here), except for the diagonal, where the distance from a vertex to itself is 0.
2. Input edges and their weights.
3. Iteratively update shortest distances:
   • For each vertex k, update the distance between all pairs (i, j) as:
     g[i][j] = min(g[i][j], g[i][k] + g[k][j])
4. After all iterations, the matrix g will hold the shortest distances between every pair.

Java Code Implementation

import java.io.*;

class Graph {
    int g[][]; // adjacency matrix
    int v, e;  // number of vertices and edges

    // Step 1: Create graph and input edges
    void Creategraph() throws IOException {
        int a, b, w;
        BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter the number of vertices");
        v = Integer.parseInt(obj.readLine());

        System.out.println("Enter number of edges");
        e = Integer.parseInt(obj.readLine());

        g = new int[v + 1][v + 1];

        // Initialize adjacency matrix
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++)
                g[i][j] = 32767; // Representing infinity
        }

        // Distance from a vertex to itself is 0
        for (int i = 1; i <= v; i++)
            g[i][i] = 0;

        // Input the edges and weights
        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;
        }
    }

    // Step 2: Apply Floyd-Warshall Algorithm
    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]);
            }
        }

        // Step 3: Display the shortest distance matrix
        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(); // Input graph data
        g.allpair();     // Compute shortest paths
    }
}

Sample Output

Enter the number of vertices: 4
Enter number of edges: 5
Enter end vertices of edge 1
1
2
Enter the weight of edge 1
2
Enter end vertices of edge 2
1
3
Enter the weight of edge 2
5
Enter end vertices of edge 3
2
4
Enter the weight of edge 3
3
Enter end vertices of edge 4
3
4
Enter the weight of edge 4
6
Enter end vertices of edge 5
1
4
Enter the weight of edge 5
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

Output Explanation

Here’s a detailed breakdown of the shortest path results:

• The algorithm tests whether an indirect route through another vertex offers a shorter distance than the current known path and updates accordingly.
• Example: From 2 → 3, no direct edge exists, but via vertex 1: (2 → 1 = 2) + (1 → 3 = 5) = 7, which becomes the shortest known path.
• All values along the diagonal remain zero since the path from a vertex to itself is always zero.

Click here for more detailed explanation of output

By the final iteration, the shortest distances between every pair are finalized based on direct and indirect paths.