1. Introduction

The Floyd-Warshall algorithm is a dynamic programming technique used to find the shortest paths between all pairs of vertices in a weighted graph. It works for both directed and undirected graphs. However, it is worth noting that if the graph contains negative cycles, then shortest paths might not exist for all pairs of nodes.

2. Program Steps

1. Initialize a matrix dist such that dist[i][j] is the shortest distance from vertex i to vertex j.

2. For each vertex i, set dist[i][i] = 0.

3. For each edge (u,v), set dist[u][v] to the weight of the edge.

4. For each vertex k, for each pair of vertices (i,j), if the vertex k is on the shortest path from i to j, then update the value of dist[i][j] to the minimum of dist[i][j] and dist[i][k] + dist[k][j].

3. Code Program

class FloydWarshall {
    final static int INF = 99999, V = 4;

    void floydWarshall(int graph[][]) {
        int dist[][] = new int[V][V];
        int i, j, k;

        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        for (k = 0; k < V; k++) {
            for (i = 0; i < V; i++) {
                for (j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        printSolution(dist);
    }

    void printSolution(int dist[][]) {
        System.out.println("Following matrix shows the shortest distances between every pair of vertices");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + "   ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int graph[][] = {{0, 5, INF, 10},
                         {INF, 0, 3, INF},
                         {INF, INF, 0, 1},
                         {INF, INF, INF, 0}};
        FloydWarshall a = new FloydWarshall();

        a.floydWarshall(graph);
    }
}

Output:

Following matrix shows the shortest distances between every pair of vertices
0   5   8   9
INF 0   3   4
INF INF 0   1
INF INF INF 0

4. Step By Step Explanation

1. INF: Represents a large number to denote infinity.

2. floydWarshall(int graph[][]): The main function that calculates the shortest distances using the Floyd-Warshall algorithm.

3. printSolution(int dist[][]): Function to print the solution.

4. Inside the floydWarshall function:

– The initial matrix is set with the input graph.

– Three nested loops represent the three main steps of the algorithm, with vertices k, i, and j being iterated through.

– For each pair (i, j), if going through vertex k makes the path shorter, then dist[i][j] is updated.

5. The main function initializes a graph and calls the floydWarshall method to calculate and print the shortest distances.

The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number of vertices in the graph.