Dijkstra(G,w,s) {
ISS(G,s);
let S be an empty set
let Q be a priority queue, initialized with V[G]
while Q is not Empty:
u<-extractMin(Q);
add u to S
for each vertex v neighbor of u
Relax(u,v,w);
}
我的问题是，为什么在 while 循环中算法的每一步中选择 Q 中所有 v 的最小 d[v] 很重要，如果我们不选择最小值会怎样？
我的意思是，从我所看到的方式来看，所有边(u，v(都会在宽度上以一阶放松(意味着如果 - s->u->v 和 (s，v( 不在 E 中，那么 (s，u( 会在 (u，v( 之前放松(，那么，为什么每次都选择最小d[v]很重要呢？
假设存在一个函数 extractMaxFiniteD(Q(，它返回顶点 v，使得它的最大 d[v] 在 Q 中是有限的
让我们假设我们将该行更改为 <-extractMaxFiniteD(Q(; 任何人都可以给我画一张图表，其中修改后的 alg 会失败 - 甚至更好 - 最短路径的哪个属性会被侵犯？
我知道这个问题可能非常困难和抽象，但如果有人1可以帮助我，那就太好了。
Dijkstra算法的主要思想是：当你从Q中取出一个顶点时，这个顶点是好的。您不必在未来放松它。
如果你从Q中获取一个随机元素，这个条件不成立 - 一旦你从Q中取出了一个顶点v，就不能保证d[v]确实是v的最短路径。
如果你采取最小值 - 这是有保证的，因为如果v在Q中最小，那么对于Q中的每个u，d[u] >= d[v]，因此无论你接下来做哪个重新定义 - 你都无法改善d[v]
示例：
节点：A、B、C
边(和权重(： (a，b，1( (a，c，10( (b，c，1(
你会发现 C 的最小成本路径是 10，而它显然是 2。
当您从 Q 中删除节点时，您不会再次放松它，如果您删除具有最大成本的节点，那么您不会考虑访问该节点的不太方便的方法。
如果您不想从 Q 中选择最小节点，那么您也不能从 Q 中删除它，您必须将其保留在集合中，以便在将来的迭代中可以放宽它。 这基本上就是贝尔曼-福特算法所做的。