【算法】图最短路径算法 —— Floyd

算法概述

弗洛伊德算法（Floyd-Warshall Algorithm）：解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

• 该算法的时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。
• 算法原理：经典的动态规划算法
  • 从任意节点 i 到任意节点 j 的最短路径：1）从 i 直接到 j；2）从 i 经过若干节点 k 到 j
  • 假设 dist(i,j) 为 i 到 j 的最短路径
  • 对于每个节点 k，检查 dist(i,k) + dist(k,j) < dist(i,j) 是否成立
  • 若成立，则设置 dist(i,j) = dist(i,k) + dist(k,j)
  • 遍历完所有节点 k 以后，dist(i,j) 记录的便是 i 到 j 的最短距离
• 算法描述：
  • 任意两点之间的距离是边的权，若两点之间没有边相连，则距离为无穷大
  • 对于节点对 (u,v)，判断是否存在节点 w 使得从 u 到 w 再到 v 比已知的路径更短，如果有便更新

动态规划思路

• 状态定义：dist[k][i][j] 为遍历前 k 个节点，获得的从 i 到 j 的最短路径
  • 经过第 k 个节点：dist[k-1][i][j]
  • 不经过第 k 个节点：dist[k-1][i][k] + dist[k-1][k][j]
• 状态转移方程：dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])
• 初始化状态：dist[0][i][j] 即为原图的邻接矩阵
• 优化关键点：
  • Floyd 算法的本质是动规，而 k 是动规的阶段，因此要写最外面
  • dist 最外层的一维空间可以省略，因为 dist[k] 只和 dist[k-1] 有关
• 优化后的状态转移方程为：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

算法实现

function floyd(nodes, edges) {
  let n = nodes.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        edges[i][j] = Math.min(edges[i][j], edges[i][k] + edges[k][j]);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(`${nodes[i]} -> ${nodes[j]}: ${edges[i][j]}`);
    }
  }
}

function formatMatrix(paths) {
  let nodes = [];
  paths.forEach((path) => {
    nodes.push(path[0], path[1]);
  });
  nodes = [...new Set(nodes)].sort();

  let edges = new Array(nodes.length);
  for (let i = 0; i < edges.length; i++) {
    edges[i] = new Array(nodes.length).fill(Infinity);
    edges[i][i] = 0;
  }

  let start = nodes[0].charCodeAt();
  paths.forEach((path) => {
    edges[path[0].charCodeAt() - start][path[1].charCodeAt() - start] = path[2];
  });

  return {
    nodes,
    edges,
  };
}

let paths = [
  ['A', 'B', 2],
  ['A', 'C', 2],
  ['B', 'C', 3],
  ['D', 'A', 1],
  ['D', 'C', 4],
];
let { nodes, edges } = formatMatrix(paths);
floyd(nodes, edges);

参考

• 图最短路径算法之弗洛伊德算法 (opens new window)
• 最短路径问题---Floyd 算法详解 (opens new window)