資料結構
網路
關係型資料庫管理系統
作業系統
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-06-15
6K+ 次檢視
廣告