最小優先度キューを持つDijkstraアルゴリズム

Question

優先度キューを使用してdijkstraアルゴリズムを実装しようとしていますが、どのように動作するのか理解できません。私はウェブ上で多くのガイドを読んだが、私はこのアルゴリズムを全く理解できない。

私の質問は次のとおりです。各ノードの優先順位は何ですか？私はそれが最小値で入縁の重さだと思うが、私は確信していない。これは本当ですか？

2番目の質問では、キューのルートを抽出すると、このノードが訪問先ノードが1つも存在しない場合の動作はどうですか？

Answer 1

vertexから最短距離のvertexが最も優先されるpriority queueを使用してください。最初に、全てverticesは無限の最短距離を有し、出発vertexはPQ内側グラフから（そのedgesで）すべてverticesを挿入することによって最短距離0

スタートを有するであろう。 PQからvertexを削除し、すべてedgesを探索してください。現在のvertexの最短距離より短い距離がある場合は、PQの中で最も近い距離をvertexに更新してください。 PQが空でない間続行します。 Verticesはedgesを得ていないので、開始点vertexから 'get to them'が可能でないため、無限遠の最短距離で終了します。ただし、それらはまだ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オープンコースウェアリンク：
Path problems overview
Dijkstra