如何证明Dijkstra算法中distance[v]≥经已处理顶点的最短s→v路径P的长度？

首先明确几个关键定义：

• 设源点为s，d(v)表示s到v的真实最短路径长度
• distance[v]是算法维护的s到v的当前路径长度估计值
• S为已处理顶点集合（不在优先队列Q中），Q为待处理顶点队列
• 待证命题：任意时刻，若存在一条最短s→v路径P，且P上除v外的所有顶点都属于S，则distance[v] ≥ length(P)（其中length(P)等于d(v)，因为P是最短路径）

我们用基于算法处理顶点次数的数学归纳法来证明：

基例：初始状态 #

初始时，S = {s}，distance[s] = 0，其余顶点distance[v] = ∞。
对于任意v，若存在满足条件的最短路径P，则P只能是直接边s→v（因为其他顶点都未处理），此时length(P)为边s→v的权重。显然∞ ≥ length(P)，基例成立。

归纳步骤 #

假设算法处理完k个顶点后，命题成立。现在证明处理第k+1个顶点后，命题仍成立：

1. 第k+1次操作从Q中取出顶点u，此时distance[u] = d(u)（这是Dijkstra算法的贪心核心性质：取出的顶点的估计值等于真实最短路径长度，可单独由贪心选择逻辑证明，无需依赖待证命题）。
2. 对u的所有邻接顶点v执行松弛操作：若distance[v] > distance[u] + w(u,v)，则更新distance[v] = distance[u] + w(u,v)（w(u,v)是边u→v的权重）。
3. 分三种情况验证命题：
   • 情况1：处理u前，v已满足命题条件：即P上除v外的顶点都在原S中。根据归纳假设，处理前distance[v] ≥ length(P)。处理u时，若v的distance未被更新，则仍满足；若被更新为distance[u] + w(u,v)，由于P是最短路径，根据三角不等式有d(v) ≤ d(u) + w(u,v)，而length(P)=d(v)、distance[u]=d(u)，因此distance[u] + w(u,v) ≥ d(v) = length(P)，更新后的distance[v]仍满足≥ length(P)。
   • 情况2：处理u后，v才满足命题条件：即P上除v外的顶点包含u，且其余顶点都在原S中。此时P可拆分为s→u的最短路径（所有顶点在原S中，故distance[u]=d(u)）加上边u→v，因此length(P) = d(u) + w(u,v)。若v的distance未被更新，根据归纳假设，原distance[v] ≥ d(v) = length(P)；若被更新，则distance[v] = d(u) + w(u,v) = length(P)，显然满足≥关系。
   • 情况3：v已在S中：此时distance[v] = d(v) = length(P)，自然满足distance[v] ≥ length(P)。

综上，归纳步骤成立，命题在算法运行的任意时刻均成立。

内容的提问来源于stack exchange，提问作者yarv