Dijkstra的Java算法
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 }