数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学JavaScript 中的 Floyd-Warshall 算法
Dijkstra 算法用于查找从一个节点到所有其他节点的最短路径的距离/路径。在某些情况下，我们需要查找从所有节点到所有其他节点的最短路径。这就是所有节点对最短路径算法派上用场的地方。最常用的所有节点对最短路径算法是 Floyd-Warshall 算法。
Floyd-Warshall 算法的工作原理如下：
- 我们初始化一个 N x N 的距离矩阵为无穷大。
- 然后，对于每条边 u, v，我们将此矩阵更新为显示此边的权重，对于边 v, v，我们将权重更新为 0。
- 我们创建三个嵌套循环，迭代器为 I、j 和 k。对于每个节点 I 到每个节点 j 的距离，我们考虑使用 k 作为中间点，如果我们找到小于现有 arr[i][j] 的距离，则更新距离。
我们不使用矩阵，而是使用对象，因为如果我们使用复杂对象来表示每个节点，则不需要跟踪索引。
现在让我们来看一下相同的实现：
示例
floydWarshallAlgorithm() {
let dist = {};
for (let i = 0; i < this.nodes.length; i++) {
dist[this.nodes[i]] = {};
// For existing edges assign the dist to be same as weight
this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
this.nodes.forEach(n => {
// For all other nodes assign it to infinity
if (dist[this.nodes[i]][n] == undefined)
dist[this.nodes[i]][n] = Infinity;
// For self edge assign dist to be 0
if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
});
}
this.nodes.forEach(i => {
this.nodes.forEach(j => {
this.nodes.forEach(k => {
// Check if going from i to k then from k to j is better
// than directly going from i to j. If yes then update
// i to j value to the new value
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 }
}
更新于：2020年6月15日
1K+ 次浏览
广告