数据结构
网络
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+ 次浏览
广告