算法设计与分析 Dij证明

RT

Def: δ(s,u): 表示从s到u的真实的最短路径 V是所有点的集合 S是已经添加的点的集合 性质1: 已经添加到S点中的点满足δ(s,x) = dist[x]

显然，对于源点s,满足该性质.对于源点s直接相连的点，亦满足。接下来就证明其他点加入到点集S时满足以下定理。(这里感觉不太严谨QAQ)

算法正确性证明:只需证明定理的正确性 定理: 在Dij算法中,顶点u被添加到S中时,dist[u] = δ(s,u)

证明: 采用反证法，实质是证明该命题的逆否命题成立. 假设对于点u被添加到S中时，dist[u] > δ(s,u). 那么存在一条路径满足路径长度 = δ(s,u)，也就是最优解，假设它为路径P 此处，x属于S，而y属于V - S.

由性质1可得: dist[x] = δ(s,x) 下面夹杂证明dist[y] = δ(s,y) 只需要证明 dist[y] >= δ(s,y) 且 dist[y] = δ(s,y),因为δ(s,y)是最优解. ②因为算法规定对于S中的点要进行边松弛操作，而x和y直接相连，所以y会被松弛。 满足dist[y]