数据结构
网络
关系型数据库管理系统
操作系统
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+ 次查看
广告