graph - 具有最小优先级队列的 Dijkstra 算法

Question

我正在尝试使用优先级队列实现 dijkstra 算法，但我不明白它是如何工作的。我在网上阅读了很多指南，但我根本无法理解这个算法。

我的问题是：每个节点的优先级是什么？我认为它是具有最小值的传入边缘的权重，但我不确定。这是真的？

第二个问题，当我提取队列的根时，如果这个节点与没有一个访问节点不相邻，它是如何工作的？

Answer 1

您应该使用距离起点最短的位置priority queue将获得最高优先级。最初，所有人的最短距离为无穷大，起点的最短距离为 0。vertexvertexverticesvertex

首先从. vertices_ 从 中删除并探索其所有. 比较所有相邻的最短距离，如果有任何距离小于当前的最短距离，则更新 中的相邻最短距离。不为空时继续。没有将以最短的无限距离结束，因为不可能从一开始就“到达他们” 。但是，它们仍将从.edgesPQvertexPQedgesverticesvertexvertexPQPQVerticesedgesvertexPQ

伪代码

initialize graph
initialize pq
pq.insertAll(graph.getVertices())

while (pq is not empty) {
  vertex = pq.remove()
  edges = vertex.getEdges()

  for all edges {
    destination = edge.getDestination()
    newDistance = edge.getLength() + vertex.getDistance()
    if (newDistance < destination.getDistance()) {
      destination.setShortestDistance(newDistance)
      pq.update(destination)
    }
  }
}

MIT OpenCourseWare 链接：
路径问题概述
Dijkstra