具有最小优先级队列的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)
    }
  }
}

麻省理工学院开放式课件链接:
路径问题概述
Dijkstra