資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法學Javascript 中的 Dijkstra 演算法
Dijkstra 演算法是尋找加權圖中節點之間最短路徑的演算法。我們使用新的 addEdge 和 addDirectedEdge 方法為建立一個圖形時的邊新增權重。我們來看看此演算法如何工作 −
- 建立一個距離集合，併除目標節點外將所有頂點距離設為無窮大。
- 將目標節點加入最小優先順序佇列，優先順序為 0，因為距離為 0。
- 開始迴圈，直到優先順序佇列為空，並從中取出距離最小的節點。
- 如果“當前節點距離 + 邊權重 < 下一個節點距離”，則將連線節點的距離更新為彈出節點的距離，然後將新距離節點推入佇列。
- 一直繼續，直到優先順序佇列為空。
此演算法的基本運作原理是假設所有節點距離目標節點的距離都是無窮大。然後它開始考慮邊，並跟蹤節點距離目標節點的距離，如果找到成本更低的路徑，則更新這些距離。
我們看看程式碼中的此實現 −
示例
djikstraAlgorithm(startNode) {
let distances = {};
// Stores the reference to previous nodes
let prev = {};
let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
// Set distances to all nodes to be infinite except startNode
distances[startNode] = 0;
pq.enqueue(startNode, 0);
this.nodes.forEach(node => {
if (node !== startNode) distances[node] = Infinity;
prev[node] = null;
});
while (!pq.isEmpty()) {
let minNode = pq.dequeue();
let currNode = minNode.data;
let weight = minNode.priority;
this.edges[currNode].forEach(neighbor => {
let alt = distances[currNode] + neighbor.weight;
if (alt < distances[neighbor.node]) {
distances[neighbor.node] = alt;
prev[neighbor.node] = currNode;
pq.enqueue(neighbor.node, distances[neighbor.node]);
}
});
}
return distances;
}你可以透過以下命令進行測試 −
示例
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C", 100);
g.addDirectedEdge("A", "B", 3);
g.addDirectedEdge("A", "D", 4);
g.addDirectedEdge("D", "C", 3);
g.addDirectedEdge("D", "E", 8);
g.addDirectedEdge("E", "F", 10);
g.addDirectedEdge("B", "G", 9);
g.addDirectedEdge("E", "G", 50);
console.log(g.djikstraAlgorithm("A"));輸出
這會產生以下輸出 −
{ A: 0, B: 3, C: 7, D: 4, E: 12, F: 22, G: 12 }
更新於： 2020 年 6 月 15 日
6K+ 次瀏覽
廣告