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