Java: Floyd Warshall Algorithm

Difficulty Level: HARD

Problem Statement:

The Floyd Warshall Algorithm is for solving all pairs of shortest-path problems. The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed Graph.

It is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm follows the dynamic programming approach to find the shortest path.

A C-function for a N x N graph is given below. The function stores the all-pair shortest path in the matrix cost [N][N]. The cost matrix of the given graph is available in cost Mat [N][N].

Input:

graph[][] = { {0,   5,  INF, 10},
              {INF,  0,  3,  INF},
              {INF, INF, 0,   1},
              {INF, INF, INF, 0} }
which represents the following graph
             10
         (0)——->(3)
          |     /|\
          5|     | 1
           |     |
          \|/    |
          (1)——->(2)
              3 

Output:

Shortest distance matrix
    0      5     8     9
   INF     0     3     4
   INF    INF    0     1 
   INF    INF   INF    0