Floyd Warshall Algorithm (All Pairs Shortest Path ) - GeeksforGeeks

https://www.quora.com/Why-is-the-order-of-the-loops-in-Floyd-Warshall-algorithm-important-to-its-correctness

Floyd-Warshall algorithm is the dynamic-programming formulation to solve all-pairs shortest paths problem. The recursive formula is given by:

where shortestPath(i,j,k) represents the shortest possible path from i to j using vertices only from the set {1,2,...,k} as intermediate points along the way.

Based on this recurrance, the bottom up procedure computes the value ofshortestPath(i,j,k) in order of increasing value of k. That means, we can find the shortest path from i to j with intermediate vertices {1,2, .. k}, if we know

• shortestPath(i,j,k-1): the shortest path from i to j with intermediate vertices {1, 2, .. k-1}
• shortestPath(i,k,k-1): the shortest path from i to k with intermediate vertices   {1, 2, .. k-1}
• shortestPath(k,j,k-1): the shortest path from k to j with intermediate vertices  {1, 2, .. k-1}

Any alteration in the nested loops will give wrong results. For example:

for(int i=0;i<n;i++) {
 for(int j=0;j<n;j++) {
  for(int k=0;k<n;k++) {
   if(dis[i][k] + dis[k][j] < dis[i][j])
   dis[i][j]= dis[i][k] + dis[k][j];
  }
 }
}

has a completely different meaning. It will give shortest path from i to j with only one intermediate vertex.

Two permutations are correct (K,I,J and K,J,I).

The order of loops in Floyd-Warshall algorithm is important because it determines the number of times you are finding distance between two given vertices.

In the correct implementation, you need to find distance between two vertices 'n' times, since you have to consider shortest distance among all possible hops (and permutations of hops). So for each k(outermost iteration), you find the distance between a pair(i,j) considering 0 to k no of hops in between.

Lets take a different order: i,j,k . In this case, for the first outermost iteration(i=0), what you find is the shortest distance from a particular source(lets call it S, for i=0) considering shortest path to a destination either directly, or considering one hop in between. However, there can be shorter routes between source to hop or/and hop to destination which you may later find out in remaining iterations(i>0), but you will never be able to modify S again since i cannot be 0 in remaining iterations. 

Hence k should be used in the outermost iteration. I believe (k,j,i) order should be fine as well

https://gopalcdas.com/2018/01/20/floyd-warshall-algorithm/

dist[][] //shortest path matrix
p[][] //predecessor matrix, used to reconstruct the path

dist[][] = ∞

for each vertex i
  dist[i][i] = 0

for each edge (i, j)
  dist[i][j] = weight(i, j)
  p[i][j] = j

for k = 1 to |V|
  for i = 1 to |V|
    for j = 1 to |V|
      if dist[i][j] > dist[i][k] + dist[k][j]
        dist[i][j] = dist[i][k] + dist[k][j]
        p[i][j] = p[i][k]

To compute the shortest path between any pair (s, t), we have considered each of the |V| vertices as intermediate points k, and chosen the cheaper between i) existing (s, t) and ii) the sum of s to k and then from k to t, meaning s to t via k.

Suppose, we want to compute dist[2][3] when k = 5.

Then, dist[2][3] = min { dist[2][3], dist[2][5] + dist[5][3] }

Here, all three distances – dist[2][3], dist[2][5] and dist[5][3] must already use intermediate nodes 1 to 4. Meaning, dist[2][5] is not the static cost set at k=0; possibly the edge cost, 0 or infinite. Rather, dist[2][5] is already computed using k from 1 to 4. Similarly, dist[5][3] (and dist[2][3] as well) is also computed using k from 1 to 4.

In other words, we cannot compute a certain dist[s][t] alone, using the intermediate nodes 1 to k. Rather for each intermediate node k, we need to compute dist[i][j] progressively, using the 3 nested loops, as shown earlier.

Path Reconstruction

The predecessor matrix p, keeps track of the shortest path. If we have to find the best path from s to t, we know for sure that we start with s. We print s. To know where we went from there, we have to look at p[s][t]. If that is t, we are done as that is the destination. However, if that is not the case, that means we find another node r. Then we know from s we went to an intermediate node r. So this becomes the new start s for the rest of the path. However, destination remains the same t. Again we look at p[s][t] and continue the same till we reach t, all along printing r (=p[s][t])

http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/
The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.
Floyd Warshall Algorithm:O(N^3)We initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and update all shortest paths which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every pair (i, j) of source and destination vertices respectively, there are two possible cases.
1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.
2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j].

Time Complexity: O(V^3)

The above program only prints the shortest distances. We can modify the solution to print the shortest paths also by storing the predecessor information in a separate 2D matrix.

// Solves the all-pairs shortest path problem using Floyd Warshall algorithm

void floydWarshell (int graph[][V])

{

    /* dist[][] will be the output matrix that will finally have the shortest

      distances between every pair of vertices */

    int dist[V][V], i, j, k;

    /* Initialize the solution matrix same as input graph matrix. Or

       we can say the initial values of shortest distances are based

       on shortest paths considering no intermediate vertex. */

    for (i = 0; i < V; i++)

        for (j = 0; j < V; j++)

            dist[i][j] = graph[i][j];

    /* Add all vertices one by one to the set of intermediate vertices.

      ---> Before start of a iteration, we have shortest distances between all

      pairs of vertices such that the shortest distances consider only the

      vertices in set {0, 1, 2, .. k-1} as intermediate vertices.

      ----> After the end of a iteration, vertex no. k is added to the set of

      intermediate vertices and the set becomes {0, 1, 2, .. k} */

    for (k = 0; k < V; k++)

    {

        // Pick all vertices as source one by one

        for (i = 0; i < V; i++)

        {

            // Pick all vertices as destination for the

            // above picked source

            for (j = 0; j < V; j++)

            {

                // If vertex k is on the shortest path from

                // i to j, then update the value of dist[i][j]

                if (dist[i][k] + dist[k][j] < dist[i][j])

                    dist[i][j] = dist[i][k] + dist[k][j];

            }

        }

    }

    // Print the shortest distance matrix

    printSolution(dist);

}

Floyd-Warshall algorithm - Algoritmy.net

public static int[][] floydWarshall(int[][] d) {

07.int[][] p = constructInitialMatixOfPredecessors(d);

08.for (int k = 0; k < d.length; k++) {

09.for (int i = 0; i < d.length; i++) {

10.for (int j = 0; j < d.length; j++) {

11.if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) {

12.continue;                 

13.}

14. 

15.if (d[i][j] > d[i][k] + d[k][j]) {

16.d[i][j] = d[i][k] + d[k][j];

17.p[i][j] = p[k][j];

18.}

19. 

20.}

21.}

22.}

23.return p;

24.}

25. 

26./**

27.* Constructs matrix P0

28.* @param d matrix of lengths

29.* @return P0

30.*/

31.private static int[][] constructInitialMatixOfPredecessors(int[][] d) {

32.int[][] p = new int[d.length][d.length];

33.for (int i = 0; i < d.length; i++) {

34.for (int j = 0; j < d.length; j++) {

35.if (d[i][j] != 0 && d[i][j] != Integer.MAX_VALUE) {

36.p[i][j] = i;

37.} else {

38.p[i][j] = -1;

39.}

40.}

41.}

42.return p;

43.}

.function getPath(P, i, j)

2.if i == j then

3.write(i)

4.else if P[i][j] = 0 then

5.write("Path does not exist")

6.else

7.getPath(P, i, P[i][j])

8.write(j)

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
the Floyd–Warshall algorithm (also known as Floyd's algorithm) is a graphanalysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles, see below) and also for finding transitive closure of a relation .

Further consider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1,2,...,k} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i to each jusing only vertices 1 to k + 1.

For each of these pairs of vertices, the true shortest path could be either (1) a path that only uses vertices in the set {1, ..., k} or (2) a path that goes from i to k + 1 and then from k + 1 to j. 

the base case is

and the recursive case is

This formula is the heart of the Floyd–Warshall algorithm. The algorithm works by first computing shortestPath(i, j, k) for all (i, j) pairs for k = 1, then k = 2, etc. This process continues until k = n, and we have found the shortest path for all (i, j) pairs using any intermediate vertices.

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

Path reconstruction

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction ()
   for each edge (u,v)
      dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
      next[u][v] ← v
   for k from 1 to |V| // standard Floyd-Warshall implementation
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]
               next[i][j] ← next[i][k]

procedure Path(u, v)
   if next[u][v] = null then
       return []
   path = [u]
   while u ≠ v
       u ← next[u][v]
       path.append(u)
   return path

Java Implementation
http://en.algoritmy.net/article/45708/Floyd-Warshall-algorithm
http://algs4.cs.princeton.edu/44sp/FloydWarshall.java.html
Read full article from Dynamic Programming | Set 16 (Floyd Warshall Algorithm) - GeeksforGeeks