Javascript中的Floyd-Warshall算法

Djikstra的算法用于查找从一个节点到所有其他节点的最短路径的距离/路径。在某些情况下，我们需要找到从所有节点到所有其他节点的最短路径。这是所有对最短路径算法派上用场的地方。最常用的所有对最短路径算法是Floyd Warshall算法。

Floyd Warshall算法的工作原理如下-

• 我们将距离的N x N矩阵初始化为Infinity。

• 然后，对于每个边u，v，我们更新此矩阵以显示该边的权重，对于边v，v，我们将权重更新为0。

• 我们使用迭代器I，j和k创建3个嵌套循环。对于每个节点我到每个节点j的距离，我们考虑使用k作为中间点，如果发现小于现有的arr [i] [j]，则更新该距离。

我们将使用一个对象，而不是使用矩阵，因为如果我们使用复杂的对象来表示每个节点，则无需跟踪索引。

现在让我们看一下相同的实现-

示例

floydWarshallAlgorithm() {
   let dist = {};
   for (let i = 0; i < this.nodes.length; i++) {
      dist[this.nodes[i]] = {};
      //对于现有的边缘，将dist设置为与weight相同
      this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
      this.nodes.forEach(n => {
         //对于所有其他节点，将其分配给infinity-
         if (dist[this.nodes[i]][n] == undefined)
         dist[this.nodes[i]][n] = Infinity;
         //对于自身边缘，将dist分配为0-
         if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
      });
   }
   this.nodes.forEach(i => {
      this.nodes.forEach(j => {
         this.nodes.forEach(k => {
            //检查从i到k再从k到j是否更好
            //而不是直接从i转到j。如果是，则更新
            //我将j值更改为新值
            if (dist[i][k] + dist[k][j] < dist[i][j])
               dist[i][j] = dist[i][k] + dist[k][j];
            });
         });
      });
      return dist;
   }
}

您可以使用以下方式进行测试：

示例

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");

g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("D", "C", 3);

console.log(g.floydWarshallAlgorithm());

输出结果

这将给出输出-

{
   A: { C: 7, B: 3, D: 4, A: 0 },
   B: { A: 3, B: 0, C: 10, D: 7 },
   C: { A: 7, D: 3, B: 10, C: 0 },
   D: { A: 4, C: 3, B: 7, D: 0 }
}