算法设计与分析 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<s…x,y…u>
此处，x属于S，而y属于V - S.

由性质1可得: dist[x] = δ(s,x)
下面夹杂证明dist[y] = δ(s,y)
只需要证明 dist[y] >= δ(s,y) 且 dist[y] <= δ(s,y)
①显然,dist[y] >= δ(s,y),因为δ(s,y)是最优解.
②因为算法规定对于S中的点要进行边松弛操作，而x和y直接相连，所以y会被松弛。
满足dist[y] <= dist[x] + w(x,y) (1)
由于P是最优解，那么它上边的路径也是最优解(即最短路).
（上课的时候赵老师已经证明了，路径A是路径B的子路径，假设A不是最优，存在A‘ < A,A’ + left < A + left = B，说明B不是最优解，与已知矛盾。）
所以满足 δ(s,y) = δ(s,x) + w(x,y) (2)
由性质1, dist[x] = δ(s,x) (3)
由(1)(2)(3),得 dist[y] <= δ(s,x) + w(x,y) = δ(s,y)
所以dist[y] <= δ(s,y)
所以dist[y] = δ(s,y)

最短路径P<s…x,y…u> 中，y出现在u之前。因此:
dist[u] > δ(s,u) >= δ(s,y) = dist[y] (4)
u != y (5)
由(4)、(5)，根据贪心选择性质，Dij将选择y点加入S而不是u点.

所以，如果dist[u] != δ(s,u), u就不会加入到S中.
逆否命题的正确性得以证明，所以原命题的正确性得到保证.
所以定理得证，Dij算法的正确性得以证明.