8第八节 图论(第4节).ppt

解： （1） d (1) (v1, v1)= 0 ， d (1) (v1, v5)= + d (1) (v1, v2)= -1 ， d (1) (v1, v6)= + d (1) (v1, v3) = -2 ， d (1) (v1, v7)= + d (1) (v1, v4) = 3 ， d (1) (v1, v8)= + （4） 停止。 v1 到 v8 的最短路径为 (v1 , v3 , v6 , v8) ，路权为 6。 6 6 0 -5 -3 v8 -5 -5 5 0 -1 v7 -1 -1 -1 7 1 0 1 v6 -3 -3 1 0 -1 v5 -7 -7 -7 3 2 0 v4 -2 -2 -2 -2 1 -5 0 -3 v3 -5 -5 -5 -1 2 0 6 v2 0 0 0 0 3 -2 -1 0 v1 t=4 t=3 t=2 t=1 v8 v7 v6 v5 v4 v3 v2 v1 d (t) (v1,vj) wij 3. Floyd 算法 （1）适合范围 Dijkstra法和逐次逼近法适合于从适合于从某一点出发，到达各点的最短路。 Floyd 算法适合于求图 D 中任意两点的最短路。 （2）算法步骤 令图的权矩阵为 D=(dij)n×n，lij 为 vi 到 vj 的距离，其中 输入权矩阵 D(0) =D。 计算 ， 中元素就是 vi 到 vj 的最短路长 例：求图中任意两点间的最短路。 v5 2 v4 v1 v2 v3 5 2 4 6 2 1 2 3 10 8 4 解：图中既有边，也有弧。将边化为两条方向相反的弧。 v5 2 v4 v1 v2 v3 5 2 4 6 2 1 2 3 10 8 4 5 5 2 2 4 4 2 2 对两矩阵中所有元素一一比较，取较小元素 对两矩阵中所有元素一一比较，取较小元素 * 第四节 最短路（链）问题 一、最短路问题的基本概念 1. 赋权有向图 给一个有向图 D=(V, A)，对 D 中的每一条弧(vi, vj)，相应地给一个数 wij，称 wij 为弧上的权，称这样的图 D 为赋权有向图。 v4 v1 v3 v2 v5 v8 v7 v6 6 3 1 2 2 1 6 10 4 10 3 6 2 2 2. 路权 在赋权有向图 D 中，给定两个顶点 vs和 vn，设P是 D 中从 vs 到 vn 的一条路，定义路 P 的权是 P 中所有弧的权之和，记为 w(P)。 v4 v1 v3 v2 v5 v8 v7 v6 6 3 1 2 2 1 6 10 4 10 3 6 2 2 此路的权值= 3+2+1+6 = 12 此路的权值= 1+10+2+2 = 15 3. 最短路问题 在赋权有向图D中，给定两个顶点 vs和 vn，求出所有从 vs 到 vn 的路中，权值最小的路 P0，即 。该问题称为最短路问题。 路 P0 的权称为从 vs 到 vn 的距离，记为 d ( vs , vn )。 注意：d (vs , vn) 与 d (vn , vs) 不一定相等。 4. 最短路问题的意义 最短路问题是重要的最优化问题之一。它可以直接应用于解决生产实际中的许多问题，如管道铺设问题、线路安排问题、厂区布局问题、设备更新问题等。 5. 最短路问题的求解方法 如果最短路能够整齐地划分为若干阶段：用动态规划方法； 如果最短路不能整齐地划分为若干阶段：用图论方法。 下面介绍二种图论方法，求解最短路问题。 注意：本节主要以有向图为例，其算法对于无向图仍然适用。 二、最短路问题的图论算法 1. Dijkstra算法 （1）适合范围 适合于图 D 中，所有弧的权 wij≥0的情况。 该算法是由 Dijkstra 于1959年提出的，当所有弧的权 wij ≥0时，该算法是公认的最好算法。 （2）基本原理 若序列 {vs,…,vn-1,vn} 是从 vs 到 vn 的最短路，则序列 {vs,…,vn-1} 必是从 vs 到 vn-1 的最短路。 （3）算法步骤 Dijkstra算法的步骤采用了为各顶点标号的方式。在标号过程中，使用了两种标号： T 标号：试探性标号（tentative label）。给一个顶点 vi 以 T 标号时，表示从 vs 到 vi 点的估计最短路权，是一种临时标号，vi 的 T 标号随时等待着变为 P 标号。 P 标号：永久性标号（permanent label）。给一个顶点 vi 以 P 标号时，表示从 vs 到 vi 点的最短路权，vi 的标号不再改变。 算法步骤： ① 给起点 vs 以 P 标号，且 P(