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 }