具有最小优先级队列的 Dijkstra 算法 [英] Dijkstra algorithm with min-priority queue

问题描述

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

I'm trying to implement the dijkstra algorithm with priority queue, but I can't understand how it works. I read many guide on the web but I can't understand this algorithm at all.

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

My questions are: What is the priority for each node? I think that it is the weight of the incoming edge with the minimum value, but I'm not sure. Is this true?

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

Second question, when I extract the root of the queue, how does it work if this node is not adjacency with no one of the visited nodes?

推荐答案

你应该使用priority queue，其中vertex与起始vertex的距离最短 将获得最高优先级.最初，所有顶点的最短距离为无穷大，起始顶点的最短距离为0.

You should use priority queue where the vertex with the shortest distance from the starting vertex will get the highest priority. Initially, all vertices will have the shortest distance of infinity and the starting vertex will have the shortest distance 0.

首先从 PQ 中插入图中的所有 vertices(及其 edges).从 PQ 中移除 vertex 并探索它的所有 edges.将最短距离与所有相邻的vertex进行比较，如果有任何距离小于当前vertex上的最短距离，则更新相邻vertex内部的最短距离PQ.当 PQ 不为空时继续.没有 edges 的 Vertices 将以最短的无穷远距离结束，因为不可能从起始 vertex '到达它们'.但是，它们仍会从 PQ 中删除.

Start by inserting of all vertices (with its edges) from the graph inside the PQ. Remove vertex from the PQ and explore all its edges. Compare the shortest distances with all adjacent vertices and if any distance is less than the shortest distance on the current vertex, update adjacent vertex shortest distance inside the PQ. Continue while PQ is not empty. Vertices which got no edges will finish with the shortest distance of infinity because it is not possible 'get to them' from the starting vertex. However, they will be still removed from the 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)
    }
  }
}

MIT 开放课件链接:
路径问题概述
Dijkstra

这篇关于具有最小优先级队列的 Dijkstra 算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！