Javascript中的Floyd-Warshall算法
Djikstra的算法用于查找从一个节点到所有其他节点的最短路径的距离/路径。在某些情况下，我们需要找到从所有节点到所有其他节点的最短路径。这是所有对最短路径算法派上用场的地方。最常用的所有对最短路径算法是FloydWarshall算法。
FloydWarshall算法的工作原理如下-
我们将距离的NxN矩阵初始化为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 }
}