最小优先级队列Dijkstra算法

Question

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

第二个问题，当我提取队列的根时，如果这个节点不与任何一个被访问的节点邻接，它将如何工作？

Answer 1

您应该使用优先级队列，其中与起始顶点距离最短的顶点将获得最高优先级。最初，所有顶点的最短距离为无穷远，起始的顶点的最短距离为0。

首先从图中插入PQ内的所有顶点（及其边)。从PQ中移除顶点，并查看其所有边。将最短距离与所有相邻的顶点进行比较，如果任何距离小于当前顶点上的最短距离，则更新PQ中相邻的顶点最短距离。当pq不为空时继续。没有边的顶点将以无穷远的最短距离结束，因为不可能从起始的顶点“到达它们”。但是，它们仍将从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)
    }
  }
}