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

Question

我正在尝试使用优先级队列实现 dijkstra 算法，但我无法理解它是如何工作的。我在网上阅读了很多指南，但我根本无法理解这个算法。
我的问题是:每个节点的优先级是什么？我认为它是具有最小值的传入边缘的权重，但我不确定。这是真的？
第二个问题，当我提取队列的根时，如果这个节点与没有一个访问节点不相邻，它是如何工作的？

Answer 1

您应该使用 priority queue vertex距离起点最短vertex将获得最高优先级。最初，所有 vertices将有最短的无限距离和起始vertex最短距离为 0。

首先插入所有vertices (及其 edges )来自 PQ 内的图表.删除 vertex来自 PQ并探索其所有edges .将最短距离与所有相邻 vertices 进行比较如果任何距离小于当前 vertex 上的最短距离, 更新相邻 vertex PQ 内最短距离.继续PQ不是空的。 Vertices没有edges将以最短的无限距离结束，因为不可能从 vertex 开始“到达他们” .但是，它们仍将从 PQ 中删除。 .

伪代码

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)
    }
  }
}

麻省理工学院开放课件链接:
Path problems overview
Dijkstra