图的最短路径算法-弗洛伊德算法

什么是Floyd-Warshall算法

如果有一个带权图，怎么才能求出图中所有顶点两两之间的最短距离？

使用之前介绍的Dijkstra算法，针对图中每一个顶点都使用一次，也可以做到求出所有顶点之间的最短距离。

但由于Dijkstra算法的代码逻辑较为复杂，所以可以使用Floyd-Warshall(弗洛伊德算法)算法做同样的事情，代码逻辑更简洁，而且两个算法求多源最短路径的总时间复杂度也相同，均为O（n^3）。

弗洛伊德算法的英文名称是Floyd-Warshall（不是心理学大师弗洛伊德），专门用于寻找带权图中多源点之间的最短路径。算法的思路是根据图实例中所有顶点，不断引入新的顶点作为中继顶点，借由一个个中继顶点，一步步推导求出所有顶点之间的最短距离。

Floyd-Warshall算法详细步骤

以下算法详细步骤图，均来自公众号”程序员小灰”的文章——《漫画：图的 “多源” 最短路径》

假设有这样一个带权图的邻接矩阵。

假设按图实例的顶点顺序，以A开始作为邻接矩阵的中继顶点:

顶点B与顶点C之间距离为无限大，此时缩短为顶点A到顶点B距离+顶点B到顶点C的距离=5+2=7。

再假设，现在接着引入新的中继顶点，以A、B作为邻接矩阵的中继顶点:

顶点A与顶点D之间距离为无限大，以顶点B作为中继顶点，此时缩短为顶点A到顶点B距离+顶点B到顶点D的距离=5+1=6。

顶点A与顶点E之间距离为无限大，以顶点B作为中继顶点，此时缩短为顶点A到顶点B距离+顶点B到顶点E的距离=5+6=11。

再假设，接着引入新的中继顶点，以A、B、C作为邻接矩阵的中继顶点:

顶点A与顶点F之间距离为无限大，以顶点C作为中继顶点，此时缩短为顶点A到顶点C距离+顶点C到顶点F的距离=2+8=10。

（注:为了简化理解，以上图解过程演示情况仅考虑了顶点A到某个顶点之间的距离，未演示其他任意顶点到某个顶点之间的距离）

重复上面的步骤，不断引入新的中继顶点，刷新邻接矩阵中的临时距离

最终得到如下图实例的距离表:

此时，距离表中记录着图中某一个顶点，到任意另外一个顶点的最短距离。

代码实现

/**
 * 最短路径算法-弗洛伊德算法
 * @param {*} graph 需要计算最短路径的图实例
 * @returns {*} 图实例(带权图)的最短路径
 */
 export const floydWarshall = graph => {
  const dist = []; //创建距离表，存储从起点到每一个顶点的距离(权值)
   const { length } = graph; //图实例的顶点数量
   // 初始化距离表为图实例每个顶点及其邻接矩阵的距离(权值)
  for (let i = 0; i < length; i++) { // 遍历图实例的所有顶点
    dist[i] = []; // 将图实例对应的顶点初始化为空矩阵
    for (let j = 0; j < length; j++) { // 循环遍历图当前顶点和其他顶点的关系(当前顶点和其他顶点是否有边)
      if (i === j) {
        // 如果是顶点到自身的距离,这距离是0
        dist[i][j] = 0;
      } else if (!isFinite(graph[i][j])) {
        // 如果这两个顶点之间没有边,就将其表示为 Infinity(无穷大)
        dist[i][j] = Infinity;
      } else {
        // 如果这两个顶点之间有边，则在距离表记录他们的距离(权值)
        dist[i][j] = graph[i][j];
      }
    }
  }
   
  //循环更新矩阵的值
  for (let k = 0; k < length; k++) { // 将顶点 0 到 k(图实例的长度) 作为中继顶点
    for (let i = 0; i < length; i++) { // 循环遍历图实例的所有顶点
      for (let j = 0; j < length; j++) { // 循环遍历图当前顶点和其他顶点的关系(当前顶点和其他顶点是否有边)
        // i 到 j 的最短路径经过 k
        if (dist[i][k] + dist[k][j] < dist[i][j]) { // 计算通过顶点 k 的 i 和 j 之间的最短路径
          // const numberToChat = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
          // console.log('k——',numberToChat[k],'i——',numberToChat[i], 'j——', numberToChat[j]);
          // console.log('dist[i][j]——',dist[i][j], 'dist[i][k]——',dist[i][k], 'dist[k][j]——', dist[k][j]);
          // console.log(`${numberToChat[i]}${numberToChat[j]}=${numberToChat[i]}${numberToChat[k]}+${numberToChat[k]}${numberToChat[j]}`);
          dist[i][j] = dist[i][k] + dist[k][j]; // 如果一个最短路径的新的值被找到，我们要使用并存储它
        }
      }
    }
  }
  return dist; // 处理完所有顶点后，返回图中所有顶点到其他顶点最短路径的结果。
};

代码实例

假如有这样一个图实例:

const graphdemo = [
  [0, 5, 2, Infinity, Infinity, Infinity, Infinity],
  [5, 0, Infinity, 1, 6, Infinity, Infinity],
  [2, Infinity, 0, 6, Infinity, 8, Infinity],
  [Infinity, 1, 6, 0, 1, 2, Infinity],
  [Infinity, 6, Infinity, 1, 0, Infinity, 7],
  [Infinity, Infinity, 8, 2, Infinity, 0, 3],
  [Infinity,Infinity,Infinity,Infinity,7,3,0]
]

加入将数组下标转换成对应顶点的辅助常量numberToChar

const numberToChar = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];

取消上述代码实现中的注释部分，并将图实例(graphdemo)传入弗洛伊德算法(floydWarshall)可以得到如下过程结果:

floydWarshall(graphdemo);
/**
VM564:28 k—— A i—— B j—— C
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 5 dist[k][j]—— 2
VM564:30 BC=BA+AC
VM564:28 k—— A i—— C j—— B
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 2 dist[k][j]—— 5
VM564:30 CB=CA+AB
VM564:28 k—— B i—— A j—— D
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 5 dist[k][j]—— 1
VM564:30 AD=AB+BD
VM564:28 k—— B i—— A j—— E
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 5 dist[k][j]—— 6
VM564:30 AE=AB+BE
VM564:28 k—— B i—— C j—— E
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 6
VM564:30 CE=CB+BE
VM564:28 k—— B i—— D j—— A
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 1 dist[k][j]—— 5
VM564:30 DA=DB+BA
VM564:28 k—— B i—— E j—— A
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 6 dist[k][j]—— 5
VM564:30 EA=EB+BA
VM564:28 k—— B i—— E j—— C
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 6 dist[k][j]—— 7
VM564:30 EC=EB+BC
VM564:28 k—— C i—— A j—— F
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 2 dist[k][j]—— 8
VM564:30 AF=AC+CF
VM564:28 k—— C i—— B j—— F
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 8
VM564:30 BF=BC+CF
VM564:28 k—— C i—— E j—— F
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 13 dist[k][j]—— 8
VM564:30 EF=EC+CF
VM564:28 k—— C i—— F j—— A
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 8 dist[k][j]—— 2
VM564:30 FA=FC+CA
VM564:28 k—— C i—— F j—— B
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 8 dist[k][j]—— 7
VM564:30 FB=FC+CB
VM564:28 k—— C i—— F j—— E
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 8 dist[k][j]—— 13
VM564:30 FE=FC+CE
VM564:28 k—— D i—— A j—— E
VM564:29 dist[i][j]—— 11 dist[i][k]—— 6 dist[k][j]—— 1
VM564:30 AE=AD+DE
VM564:28 k—— D i—— A j—— F
VM564:29 dist[i][j]—— 10 dist[i][k]—— 6 dist[k][j]—— 2
VM564:30 AF=AD+DF
VM564:28 k—— D i—— B j—— E
VM564:29 dist[i][j]—— 6 dist[i][k]—— 1 dist[k][j]—— 1
VM564:30 BE=BD+DE
VM564:28 k—— D i—— B j—— F
VM564:29 dist[i][j]—— 15 dist[i][k]—— 1 dist[k][j]—— 2
VM564:30 BF=BD+DF
VM564:28 k—— D i—— C j—— E
VM564:29 dist[i][j]—— 13 dist[i][k]—— 6 dist[k][j]—— 1
VM564:30 CE=CD+DE
VM564:28 k—— D i—— E j—— A
VM564:29 dist[i][j]—— 11 dist[i][k]—— 1 dist[k][j]—— 6
VM564:30 EA=ED+DA
VM564:28 k—— D i—— E j—— B
VM564:29 dist[i][j]—— 6 dist[i][k]—— 1 dist[k][j]—— 1
VM564:30 EB=ED+DB
VM564:28 k—— D i—— E j—— C
VM564:29 dist[i][j]—— 13 dist[i][k]—— 1 dist[k][j]—— 6
VM564:30 EC=ED+DC
VM564:28 k—— D i—— E j—— F
VM564:29 dist[i][j]—— 21 dist[i][k]—— 1 dist[k][j]—— 2
VM564:30 EF=ED+DF
VM564:28 k—— D i—— F j—— A
VM564:29 dist[i][j]—— 10 dist[i][k]—— 2 dist[k][j]—— 6
VM564:30 FA=FD+DA
VM564:28 k—— D i—— F j—— B
VM564:29 dist[i][j]—— 15 dist[i][k]—— 2 dist[k][j]—— 1
VM564:30 FB=FD+DB
VM564:28 k—— D i—— F j—— E
VM564:29 dist[i][j]—— 21 dist[i][k]—— 2 dist[k][j]—— 1
VM564:30 FE=FD+DE
VM564:28 k—— E i—— A j—— G
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 7
VM564:30 AG=AE+EG
VM564:28 k—— E i—— B j—— G
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 2 dist[k][j]—— 7
VM564:30 BG=BE+EG
VM564:28 k—— E i—— C j—— G
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 7
VM564:30 CG=CE+EG
VM564:28 k—— E i—— D j—— G
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 1 dist[k][j]—— 7
VM564:30 DG=DE+EG
VM564:28 k—— E i—— G j—— A
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 7
VM564:30 GA=GE+EA
VM564:28 k—— E i—— G j—— B
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 2
VM564:30 GB=GE+EB
VM564:28 k—— E i—— G j—— C
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 7
VM564:30 GC=GE+EC
VM564:28 k—— E i—— G j—— D
VM564:29 dist[i][j]—— Infinity dist[i][k]—— 7 dist[k][j]—— 1
VM564:30 GD=GE+ED
VM564:28 k—— F i—— A j—— G
VM564:29 dist[i][j]—— 14 dist[i][k]—— 8 dist[k][j]—— 3
VM564:30 AG=AF+FG
VM564:28 k—— F i—— B j—— G
VM564:29 dist[i][j]—— 9 dist[i][k]—— 3 dist[k][j]—— 3
VM564:30 BG=BF+FG
VM564:28 k—— F i—— C j—— G
VM564:29 dist[i][j]—— 14 dist[i][k]—— 8 dist[k][j]—— 3
VM564:30 CG=CF+FG
VM564:28 k—— F i—— D j—— G
VM564:29 dist[i][j]—— 8 dist[i][k]—— 2 dist[k][j]—— 3
VM564:30 DG=DF+FG
VM564:28 k—— F i—— E j—— G
VM564:29 dist[i][j]—— 7 dist[i][k]—— 3 dist[k][j]—— 3
VM564:30 EG=EF+FG
VM564:28 k—— F i—— G j—— A
VM564:29 dist[i][j]—— 14 dist[i][k]—— 3 dist[k][j]—— 8
VM564:30 GA=GF+FA
VM564:28 k—— F i—— G j—— B
VM564:29 dist[i][j]—— 9 dist[i][k]—— 3 dist[k][j]—— 3
VM564:30 GB=GF+FB
VM564:28 k—— F i—— G j—— C
VM564:29 dist[i][j]—— 14 dist[i][k]—— 3 dist[k][j]—— 8
VM564:30 GC=GF+FC
VM564:28 k—— F i—— G j—— D
VM564:29 dist[i][j]—— 8 dist[i][k]—— 3 dist[k][j]—— 2
VM564:30 GD=GF+FD
VM564:28 k—— F i—— G j—— E
VM564:29 dist[i][j]—— 7 dist[i][k]—— 3 dist[k][j]—— 3
VM564:30 GE=GF+FE
**/

/**
return后，dist的结果:
[
    [0,5,2,6,7,8,11],
    [5,0,7,1,2,3,6],
    [2,7,0,6,7,8,11],
    [6,1,6,0,1,2,5],
    [7,2,7,1,0,3,6],
    [8,3,8,2,3,0,3],
    [11,6,11,5,6,3,0]
]
**/