在第 24 章第 658 页 CLRS 第三版中的 DIJKSTRA 伪代码中,在内部循环中,从新添加的顶点放松相邻边时,为什么允许边上的放松已经从队列中取出并添加到树的最短路径?
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)
}
哪个是正确的方法?