证明前驱子图Gπ,i是以i为根的一个最短路径树，需要依次证明如下性质：
1. Gπ,i没有环路
2. i到Gπ,i中任意顶点有且只有一条路径
3. 证明该路径为最短路径
性质1证明
πi,j=k, 则di,j <= di,k + w(k,j), 假设存在环路c为(v0, v1, v2,...vk), vk=v0, 且是在更新vi的π值时第一次形成的环, π(vi)=vi-1 ，根据π的定义
对于vi有di,vi < di,vi-1 + w(vi-1, vi)
将k-1个不等式和上面的严格不等式相加得到 0 > w(v0, v1) + ... + v(vk, v0)，和没有负权环路的前提矛盾
性质2证明
a. 存在性证明：归纳法证明，可以证明在修改π时仍然保持该性质
b. 唯一性证明：由于假设存在i--->j的两条路径p1和p2, p1为i-->x->z-->j, p2为i--->y->z--->j, (x,y,z)这样的三个点总是存在的， 由于π[i,z]值唯一，与x,y不同矛盾
性质3证明
由于d[i,j]为i到j的最短路径，而且根据d[i,j]的计算方式可得d[i,j] = len(i--->j)，因此该路径为最短路径
转载于:https://www.cnblogs.com/ellusak/archive/2012/07/30/2614546.html
相关资源：算法导论（正宗中文第三版）3-1