Dijkstra算法和最小优先队列

Question

我正在尝试使用优先队列实现迪杰斯特拉算法，但是我不理解它的工作原理。我在网上阅读了很多指南，但是我根本不理解这个算法。

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

第二个问题，当我提取队列的根时，如果该节点与任何已访问节点都不相邻，它如何工作？

- giacomotb

---

如果你把Dijkstra算法看作是“加权图的广度优先搜索”，那么它就变得相当容易理解了。回答你的问题：1. 不完全是这样——它是到目前为止遍历过的边的最小值。2. 就像BFS一样，如果一个节点不与已访问节点相邻，则它暂时不能被访问。如果它从已访问节点不可达，则永远不会被访问。 - BlueRaja - Danny Pflughoeft

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

麻省理工学院开放式课程链接：
路径问题概述
Dijkstra算法

- Patrik Fuhrmann

---

我不明白的一件事是如何跟踪较短的边缘？在这个例子中，似乎你只剩下了最终的最短距离（newDistance），而不是顶点列表？ - Chris Stryczynski