参考文档：Floyd Warshall Algorithm | DP-16

Floyd算法介绍

和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

基本思想

通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

假设图G中顶点个数为N，则需要对矩阵S进行N次更新。

初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。

接下来开始，对矩阵S进行N次更新。

第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]“(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]“。

同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k]+a[k][j]“，则更新a[i][j]为”a[i][k]+a[k][j]“。更新N次之后，操作完成！

单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。

Floyd算法图解

Floyd Warshall Algorithm - 图1

以上图G4为例，来对弗洛伊德进行算法演示。

Floyd Warshall Algorithm - 图2

初始状态：S是记录各个顶点间最短路径的矩阵。

第1步：初始化S。

矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。实际上，就是将图的原始矩阵复制到S中。

注:a[i][j]表示矩阵S中顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

第2步：以顶点A(第1个顶点)为中介点，若a[i][j] > a[i][0]+a[0][j]，则设置a[i][j]=a[i][0]+a[0][j]。

以顶点a[1][6](即顶点B和顶点G之间的距离为例)，上一步操作之后，a[1][6]=∞；而将A作为中介点时，(B,A)=12，(A,G)=14，因此B和G之间的距离可以更新为26。

同理，依次将顶点B,C,D,E,F,G作为中介点，并更新a[i][j]的大小。

Floyd算法的代码说明

以”邻接矩阵”为例对弗洛伊德算法进行说明，对于”邻接表”实现的图在后面会给出相应的源码。

  1. // C++ Program for Floyd Warshall Algorithm
  2. #include <bits/stdc++.h>
  3. using namespace std;
  5. // Number of vertices in the graph
  6. #define V 4
  8. /* Define Infinite as a large enough
  9. value.This value will be used for
  10. vertices not connected to each other */
  11. #define INF 99999
  13. // A function to print the solution matrix
  14. void printSolution(int dist[][V]);
  16. // Solves the all-pairs shortest path
  17. // problem using Floyd Warshall algorithm
  18. void floydWarshall(int graph[][V])
  19. {
  20.     /* dist[][] will be the output matrix
  21.     that will finally have the shortest
  22.     distances between every pair of vertices */
  23.     int dist[V][V], i, j, k;
  25.     /* Initialize the solution matrix same
  26.     as input graph matrix. Or we can say
  27.     the initial values of shortest distances
  28.     are based on shortest paths considering
  29.     no intermediate vertex. */
  30.     for (i = 0; i < V; i++)
  31.         for (j = 0; j < V; j++)
  32.             dist[i][j] = graph[i][j];
  34.     /* Add all vertices one by one to
  35.     the set of intermediate vertices.
  36.     ---> Before start of an iteration,
  37.     we have shortest distances between all
  38.     pairs of vertices such that the
  39.     shortest distances consider only the
  40.     vertices in set {0, 1, 2, .. k-1} as
  41.     intermediate vertices.
  42.     ----> After the end of an iteration,
  43.     vertex no. k is added to the set of
  44.     intermediate vertices and the set becomes {0, 1, 2, ..
  45.     k} */
  46.     for (k = 0; k < V; k++) {
  47.         // Pick all vertices as source one by one
  48.         for (i = 0; i < V; i++) {
  49.             // Pick all vertices as destination for the
  50.             // above picked source
  51.             for (j = 0; j < V; j++) {
  52.                 // If vertex k is on the shortest path from
  53.                 // i to j, then update the value of
  54.                 // dist[i][j]
  55.                 if (dist[i][j] > (dist[i][k] + dist[k][j]))
  56.                     dist[i][j] = dist[i][k] + dist[k][j];
  57.             }
  58.         }
  59.     }
  61.     // Print the shortest distance matrix
  62.     printSolution(dist);
  63. }
  65. /* A utility function to print solution */
  66. void printSolution(int dist[][V])
  67. {
  68.     cout << "The following matrix shows the shortest "
  69.             "distances"
  70.             " between every pair of vertices \n";
  71.     for (int i = 0; i < V; i++) {
  72.         for (int j = 0; j < V; j++) {
  73.             if (dist[i][j] == INF)
  74.                 cout << "INF"
  75.                     << "     ";
  76.             else
  77.                 cout << dist[i][j] << "     ";
  78.         }
  79.         cout << endl;
  80.     }
  81. }
  83. // Driver code
  84. int main()
  85. {
  86.     /* Let us create the following weighted graph
  87.             10
  88.     (0)------->(3)
  89.         |     /|\
  90.     5 |     |
  91.         |     | 1
  92.     \|/     |
  93.     (1)------->(2)
  94.             3     */
  95.     int graph[V][V] = { { 0, 5, INF, 10 },
  96.                         { INF, 0, 3, INF },
  97.                         { INF, INF, 0, 1 },
  98.                         { INF, INF, INF, 0 } };
  100.     // Print the solution
  101.     floydWarshall(graph);
  102.     return 0;
  103. }
  105. // This code is contributed by Mythri J L

最大距离说明

标准 Dijkstra 算法是计算最短路径的，但你有想过为什么 Dijkstra 算法不允许存在负权重边么？

因为 Dijkstra 计算最短路径的正确性依赖一个前提：路径中每增加一条边，路径的总权重就会增加。

如果你想计算最长路径，路径中每增加一条边，路径的总权重就会减少，要是能够满足这个条件，也可以用 Dijkstra 算法。

同理，Floyd算法同样求最长路径，只需要改成

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