拓扑排序算法示例.PPT

* 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 第七章 图 * 0 1 2 3 4 5 0 1 2 3 4 5 ∞ 50 10 ∞ 45 ∞ ∞ ∞ 15 ∞ 10 ∞ 20 ∞ ∞ 15 ∞ ∞ ∞ 20 ∞ ∞ 35 ∞ ∞ ∞ ∞ 30 ∞ ∞ ∞ ∞ ∞ 3 ∞ ∞ v 0 v 2 v 5 v 4 v 1 v 3 20 15 3 10 50 10 45 15 35 30 20 7.6.1 求某一顶点(源点)到其它各顶点的最短路径 单源点的最短路径问题：给定带权有向图G和源点（路径上的第一个顶点）v0，求从v0到G中其余各点的最短路径。 * v 0 v 2 v 5 v 4 v 1 v 3 20 15 3 10 50 10 45 15 35 30 20 * 迪杰斯特拉提出了一个按路径长度递增的次序产生最短路径的算法。 首先引入辅助向量D， 其每个分量D[i]表示当前所找到的从源点v0到每个终点vi的最短路径的长度。 初始时，若从v0到vi 有弧，则D[i]为弧上的权值，否则为∞。显然，长度为 D[j]=Min{D[i] | vi ∈ V} 的路径就是从v0出发的长度最短的一条最短路径，即 (v0, vj)。 那么下一条长度次短的最短路径是哪一条呢？ * 一般情况下，假设S为已求得最短路径的顶点的集合，开始为{v0}。我们可以证明： 下一条长度次短的最短路径 (设其终点为vx) 或者是弧（v0，vx），或者是中间经过S中的顶点而后到达vx的路径。  * 可用反证法： 假设下一条最短路径上有一个顶点vy不在S中，即此路径为（v0，…，vy，…，vx）。 显然，（v0，…，vy）的长度小于（v0，…，vy，…，vx）的长度，故下一条最短路径应为（v0，…，vy），这与假设的下一条最短路径（v0，…，vy，…， vx）相矛盾！ 因此，下一条最短路径上不可能有不在S中的顶点vy，即假设不成立。 * 一般情况下，下一条长度次短的最短路径的长度必是 D[j] = Min{D[i] | vi∈V－S} 其中，D[i]或者是弧（v0，vi）上的权值， 或者是D[k]（vk∈S）和弧（vk，vi）上的权值之和。 由于图中的顶点分为两组：  S——已求出的最短路径的终点集合(开始为{v0})  V-S——尚未求出最短路径的顶点集合(开始为V－{v0}的全部结点) 可以按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中。 * 迪杰斯特拉算法的应用演示与迪杰斯特拉算法最相关的性质是: 如果按照长度递增的顺序来产生各个最短路径，设S为已经求得的最短路径的终点集合,下一条长度次短的最短路径 (设其终点为vx) 或者是弧（v0，vx），或中间经过S中的顶点而后到达vx的路径。  * S V0 V-S V1，V2，V3，V4，V5 1.1 假设当前从V0出发的最短路径的终点是V2，则将V2加入S，同时修改V0到V-S 中剩余各点的路径长度。 S V0 V2 V-S V1， V3，V4，V5 0.1 初始时， S={V0}，V-S={V1，V2，V3，V4，V5}，从V0到V-S 中剩余各点Vi的路径长度分别为g.arcs[0][i]。 * S V0 V2 V-S V1， V3，V4，V5 1.2 修改过程如下：以求取V0到V1的最短路径长度为例，如果二者之间存在一条路径（V0,V2,V1）的长度比当前（V0,V1）的弧长更短，则用（V0,V2,V1）替代（V0,V1）, 成为新的V0到V1的最短路径。 1.3 修改V0到V3， V0到V4， V0到V5的最短路径长度依此操作。 2.1 此轮操作完成后，若当前最短路径中的终点是V4，则将V4加入S，同时修改V0到V-S 中剩余各点的路径长度 * S V0 V2 V4 V-S V1， V3， V5 2.2 修改过程如下：以求取V0到V1的最短路径长度为例，如果二者之间存在一条路径（V0,…,V4,V1）的长度比当前V0到V1的最短路径更短，则使（V0,…,V4,V1）成为新的V0到V1的最短路径。 2.3 修改V0到V3， V0到V5的最短路径长度依此操作。 3.1 此轮操作完成后，若当前最短路径中的终点是V3，则将V3加入S，同时修改V0到V-S 中剩余各点的路径长