图论:最短路径的表示

给定一个图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, 使得

  1. V’是G中从s可达的一组顶点
  2. G’形成根为s的根树, 并且
  3. 对于所有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)。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?