All Pairs Shortest Path problem

find shortest distances between every pair of vertices in a given edge weighted directed Graph.
edge are positive

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       
Note that the value of graph[i][j] is 0 if i is equal to j 
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.

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

点i和点j 之间的shortest path

dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])) <- dp[i][k]
and dp[k][j] must compute before dp[i][j]

k is from 0 to V-1 在这块儿，需要分析一下，因为一般我们都是对dp[i][j] 计算最优，然后move on to next vertex。 但是这里行不通。
换个思路：当我们使每个点做为中转点， 第k个点做i到j的intermediate点，计算dp[i][j] 。k是从0到V-1
如果shortestPath[1][2] =shortestPath[1][3] +   shortestPath[3][2]
而shortestPath[1][3] =shortestPath[1][5] +   shortestPath[5][3]
这种情况k=5在k=3之后计算
那么shortestPath[1][2] =shortestPath[1][5] +   shortestPath[5][2]

   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];  
     /* 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];  
         }  
       }  
     }  
 
   }