单源最优路径正确性证明

单源最优路径正确性证明

参考博客

单源最短路径的算法思想：
路径树：源结点到其他任意结点的最优路径。
在当前路径树中，可到的第一结点距离最短，则加入路径树，直到所有结点被添加进路径树中。

证明该策略的正确性
令结点集合为 V mathbf V V，已经在最短路径树当中的结点的集合为 S mathbf S S
贪心选择性质：
s s s 到 v v v 只经过 S mathbf S S 中的结点路径最短（或理解为 S mathbf S S 到周边可到第一结点，且距离最短？），即：
v = arg min ⁡ v ′ ∈ V ∖ S d i s t ( s , v ′ , S ) v = argmin_{v' in mathbf V setminus mathbf S} dist(s, v', S) v=v′∈V∖Sargmin​dist(s,v′,S)
反证法。假设存在另一条路径经过了 V ∖ S mathbf V setminus mathbf S V∖S 中的结点，再到 v v v，其路径长度为 d i s t ( s , v , V ) < d i s t ( s , v , S ) dist(s, v, mathbf V) < dist(s, v, mathbf S) dist(s,v,V)

最优子结构：
令 v = arg min ⁡ v ′ ∈ V d i s t ( s , v ′ , S ) v = argmin_{v' in mathbf V} dist(s, v', mathbf S) v=v′∈Vargmin​dist(s,v′,S) ，即 v v v 是最后一个放入 S mathbf S S 的结点，又令 T mathbf T T 为以 S mathbf S S 为根结点的最优树，即任意最短路径只经过 T mathbf T T，需证明： T 1 = T ∖ { v } mathbf T_1 = mathbf T setminus {v} T1​=T∖{v} 是 V ∖ { v } mathbf V setminus {v} V∖{v} 的最优树。
反证法。
令 T 2 mathbf T_2 T2​ 是 V ∖ { v } mathbf V setminus {v} V∖{v} 的最优树，则存在一个结点，使得 d i s t ( s , x , T 2 ) < d i s t ( s , x , T 1 ) dist(s, x, mathbf T_2) < dist(s, x, mathbf T_1) dist(s,x,T2​)

---

失败作：

结点 V = { v 1 , v 2 , … , v m } mathbf V = {v_1, v_2, dots, v_m} V={v1​,v2​,…,vm​}
默认出发结点为 v 1 v_1 v1​， D ( v ) D(v) D(v) 为结点 v 1 v_1 v1​ 到结点 v v v 的最优路径长度。

证明贪心选择性质
有路径 P = { v 1 , … , v i , v j } mathbf P = {v_1, dots ,v_i, v_j} P={v1​,…,vi​,vj​} 为结点 v 1 v_1 v1​ 到结点 v j v_j vj​ 的最优路径， 那么证明 P = { v 1 , … , v i } mathbf P = {v_1, dots ,v_i} P={v1​,…,vi​} 为结点 v 1 v_1 v1​ 到结点 v i v_i vi​ 的最优路径。

证明最优子结构
有路径 P = { v 1 , … , v i , v j } mathbf P = {v_1, dots ,v_i, v_j} P={v1​,…,vi​,vj​} 为结点 v 1 v_1 v1​ 到结点 v j v_j vj​ 的最优路径， 那么证明 P = { v 1 , … , v i } mathbf P = {v_1, dots ,v_i} P={v1​,…,vi​} 为结点 v 1 v_1 v1​ 到结点 v i v_i vi​ 的最优路径。
D ( v j ) = D ( v ) D(v_j) = D(v) D(vj​)=D(v)