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

问题描述

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

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

第二个问题，当我提取队列的根时，如果这个节点不是没有访问节点的邻接关系，那么这个节点是如何工作的？

解决方案您应该使用优先级队列，其中顶点与最初距离顶点的最短距离将获得最高优先级。最初，所有顶点将具有最短的无限距离，并且起始顶点将具有最短距离0。 p>

首先插入所有顶点（使用它的边）从 PQ 中的图表。从 PQ 中删除​​ vertex 并探索所有的边缘。将最短距离与所有相邻的顶点进行比较，如果任何距离小于当前顶点的最短距离，则更新相邻顶点 PQ 内的最短距离。继续，而 PQ 不为空。 没有边缘的顶点将会以无限远的最短距离完成，因为它不可能从'get to them'起点顶点。但是，它们仍会从 PQ 中移除。

$ b

伪代码

 初始化图
初始化pq 
 pq.insertAll（graph.getVertices（））
 
（pq不为空）{
 vertex = pq.remove（）
 edges = vertex.getEdges（）
 
用于所有边{
 destination = edge .getDestination（）
 newDistance = edge.getLength（）+ vertex.getDistance（）
 if（newDistance< destination.getDistance（））{
 destination.setShortestDistance（newDistance）
 pq.update（destination）
} 
} 
} 
  

麻省理工学院开放式课件链接：

路径问题概述

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 question are: what is the priority for each node? I think that it is the weight of the incoming edge with minimun value, but I'm not sure. Is this true?

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

解决方案

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.

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.

Pseudocode

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 OpenCourseWare Links:
Path problems overview
Dijkstra

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