Javascript 中的 Dijkstra 算法
web developmentfront end technologyjavascript
Dijkstra 算法是一种用于查找加权图中节点之间最短路径的算法。我们将使用新的 addEdge 和 addDirectedEdge 方法在创建图时向边添加权重。让我们看看这个算法是如何工作的 −
- 创建一个距离集合，并将除源节点之外的所有顶点距离设置为无穷大。
- 将源节点排入优先级为 0 的最小优先级队列，因为距离为 0。
- 开始循环，直到优先级队列为空，然后将与其距离最小的节点出队。
- 如果"当前节点距离 + 边权重 <，则更新连接节点与弹出节点的距离下一个节点距离"，然后将具有新距离的节点推送到队列。
- 继续，直到优先级队列为空。
该算法的基本作用是假设所有节点与源的距离都是无限的。然后它开始考虑边缘，并跟踪节点与源的距离，如果沿途找到成本较低的路径，则更新距离。
让我们在代码中查看此实现 −
示例
djikstraAlgorithm(startNode) {
let distances = {};
// 存储对前一个节点的引用
let prev = {};
let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
// 将到除 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 }
