algorithm - 在 Dijkstra 算法中每次迭代将选择具有最小距离值的顶点的引理是什么？

Question

这是来自维基百科的伪代码:

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Node with the least distance will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]

这是一个贪婪的过程。令我困惑的是第 13 行:为什么必须先选择距离最小的节点？它背后的理论或引理是什么？

修改:

在u从Q中提取之前，dist[u]是INFINITY，或者对应Yonggoo Noh提到的论文中u的“估计距离”

Answer 1

您可以轻松找到 Dijkstra 算法的证明。

其中一个是:http://web.cs.ucdavis.edu/~amenta/w10/dijkstra.pdf

在该链接中，

Lemma 2 Let v_m be an outside vertex in V−S such that d_m is minimum. Then d_m ≤ d_j , for all j ∈ V−S. That is, the estimated distance to v_m is a lower bound on the length of the shortest path from s to any vertex in V−S.

有关 Dijkstra 的详细证明，请参阅该链接。