Dijkstra算法属性

Question

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的MINIMUM d [v]是很重要的,如果我们不选择最小值,那么会怎样？

我的意思是从我看到的方式来看,所有边缘(u,v)都会以宽度第一顺序放松(意味着如果 - s-> u-> v和(s,v)不在E中那么(s, u)在(u,v)之前会放松,所以为什么每次选择最小d [v]很重要？

假设存在一个函数extractMaxFiniteD(Q),它返回顶点v,使得它具有Q中有限的max d [v]

假设我们将该行更改为u <-extractMaxFiniteD(Q); 任何人都可以画出一个图表,其中修改后的alg会失败 - 甚至更好 - 最短路径的属性会变得暴力吗？

我知道这个问题可能非常困难和抽象,但如果某些人可以帮助我,那将会很棒.

Answer 1

Dijkstra算法的主要思想是:当你取出一个顶点时Q,这个顶点是好的.您不必在fututre放松身心.

如果你从中取一个随机元素Q,这个条件就不成立 - 一旦你把一个顶点v拿出来Q,就不能保证d[v]它确实是最短的路径v.

如果你花最少的-它是有保证的,因为如果v是在最小Q,然后为每个u在Q,d[u] >= d[v],因此无论哪个relexations你做未来的-你不能改善d[v]