資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 中的 Floyd-Warshall 演算法
迪傑斯特拉演算法用於查詢從一個節點到所有其他節點的最短路徑的距離/路徑。在某些情況下，我們需要查詢從所有節點到所有其他節點的最短路徑。這就是所有對最短路徑演算法派上用場的地方。最常用的所有對最短路徑演算法是 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+ 瀏覽量
廣告