folyd-warshall是求最短路径的算法，它的功能比较强大，可以求任意两点的最短距离。 它是一种动态规划的算法，floyd-warshall与dijkstra算法有着很大的区别： 1.结果上，dijkstra是求得一点到任一点的最短距离（一维数组），而floyd-warshall的结果是任意两点之间的最短距离（二维数组）。 2.思想上，dijkstra是从给定源点开始，比较源点到当前点所有可达的点的距离，找出最小的距离，这个最小的距离上的最后一个点，就是源点到最后一个点的最短距离，然后再把最后一个点作为当前点进行迭代，每次都要找最短距离，体现了该算法的贪心思想；floyd-warshall是动态地更新任意两点之间的最短距离，怎么才能更新呢，那就要找到第三个点，比如说要更新AB两点之间的最短距离，那就拿第三个点P，看看是否AP的距离+PB的距离是否小于AB的距离，如果小于，则更新AB的距离，这采用了动态规划的思想。
以下是floyd-warshall算法的js代码
const initDistanceAndPath = (graph) => { const n = graph.length; const distance = []; const path = []; for (let i = 0; i < n; i++) { distance[i] = []; path[i] = []; for (let j = 0; j < n; j++) { if (i === j) { distance[i][j] = 0; path[i][j] = [i]; } else if (graph[i][j] === 0) { distance[i][j] = Infinity; path[i][j] = []; } else { distance[i][j] = graph[i][j]; path[i][j] = [i, j]; } } } return { distance, path }; } const floydWarshall = (graph) => { const { distance, path } = initDistanceAndPath(graph); const n = graph.length; for (let k = 0; k < n; k++) { for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (distance[i][j] > distance[i][k] + distance[k][j]) { distance[i][j] = distance[i][k] + distance[k][j]; path[i][j] = path[i][k].concat(path[k][j][1]); } } } } return { distance, path }; } const graph = [[0, 2, 4, 0, 0, 0], [0, 0, 2, 4, 2, 0], [0, 0, 0, 0, 3, 0], [0, 0, 0, 0, 0, 2], [0, 0, 0, 3, 0, 2], [0, 0, 0, 0, 0, 0]]; console.log(floydWarshall(graph));