1

第 24 章の DIJKSTRA 疑似コード 658 ページの CLRS 第 3 版では、内側のループで、新しく追加された頂点から隣接するエッジを緩和しながら、キューから既にデキューされ、ツリーへの最短パスに追加されたエッジで緩和が許可されるのはなぜですか?

while(Q not empty){
 u = extractMin from Q;
 Add S to the shortest path tree;
 for each vertex v adjacent to u 
 relax(u,v,w)

}

内側のループが、頂点が既に最短パス ツリーの一部であるかどうかを確認しないのはなぜですか。

while(Q not empty){
     u = extractMin from Q;
     Add S to the shortest path tree;
     for each vertex v adjacent to u 
     if v is in Q 
      then relax(u,v,w)

    }

正しいアプローチはどれですか？

4

2 に答える 2