图论（最短路径的表示） _最短路径的表示

给定一个图G =（V, E）, 我们为每个顶点v∈V维持一个前驱体π[v], 它可以是另一个顶点或NIL。但是, 在执行最短路径算法期间, π值不必表示最短路径。如在广度优先搜索中一样, 我们将对值π引起的前一子图Gn =（Vn, En）感兴趣。再一次, 我们将顶点集Vπ定义为具有非NIL前身的G顶点集以及源s：

Vπ= {v ∈ V: π [v] ≠ NIL} ∪ {s} }

有向边集EΠ是由VΠ中顶点的Π值引起的边集：

EΠ= {(Π[v], v) ∈ E: v ∈ VΠ - {s}}

根于s的最短路径树是有向子图G =（V’ E’ ）, 其中V’ ∈V和E’ ∈E, 使得

V’ 是G中从s可达的一组顶点
G’ 形成根为s的根树, 并且
对于所有v∈V’ , G中从s到v的唯一简单路径是G中从s到v的最短路径。

最短路径并不是天生唯一的, 也不是最短路径树。
最短路径的属性 1.最佳子结构属性：最短路径的所有子路径都是最短路径。

文章图片
令P1为最短s-v路径的x-y子路径。令P2为任意x-y路径。那么P1的成本≤P2的成本, 否则P不是最短的s-v路径。
2.三角不等式：令d（v, w）为从v到w的最短路径的长度。则d（v, w）≤d（v, x）+ d（x, w）

文章图片
3.上限属性：对于所有顶点v∈V, 我们总是具有d [v]≥δ（s, v）, 并且一旦d [v]得出值δ（s, v）, 它就永远不会改变。
4.无路径属性：如果没有从s到v的路径, 则我们通常有d [v] =δ（s, v）=∞。
【图论（最短路径的表示）】5.收敛性：如果s-> u-> v是G在某些u上的最短路径, 则v∈V, 并且如果d [u] =δ（s, u）在松弛边（u, v）, 则之后的所有时间d [v] =δ（s, v）。