第七题最短路.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)= + 解： （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)= + * * 2. 逐次逼近算法 （1）适合范围 适合于图 D 中，存在负权弧的情况，即存在wij≤0的情况。 （2）基本原理 从 vs 到 vj 的最短路总是从 vs 出发，沿着一条路 P 到 vi 后，再沿 (vi , vj) 到vj，则从 vs 到 vi 的这条路 P 必定是从 vs 到 vi 的最短路。 所以，d ( vs , vj ) 必须满足如下方程： （3）算法步骤 ① ② 2. 逐次逼近算法 （1）适合范围 适合于图 D 中，存在负权弧的情况，即存在wij≤0的情况。 （2）基本原理 从 vs 到 vj 的最短路总是从 vs 出发，沿着一条路 P 到 vi 后，再沿 (vi , vj) 到vj，则从 vs 到 vi 的这条路 P 必定是从 vs 到 vi 的最短路。 所以，d ( vs , vj ) 必须满足如下方程： （3）算法步骤 ① ② ③ 当 t = k 时，对所有 j =1, 2 , … , p(D) 满足： 停止跌代， ，则即从 vs 为到各点的最短路。 例：求从 v1 到各点的最短路。 v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 d(2)(v1,v1)= v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 （2） v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 （3） （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 ③ 当 t = k 时，对所有 j =1, 2 , … , p(D) 满足： 停止跌代， ，则即从 vs 为到各点的最短路。 例：求从 v1 到各点的最短路。 v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 d(2)(v1,v1)= v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1 （2） v4 v1 v3 v2 v5 v8 v7 6 -1 8 -5 -3 -1 1 2 7 -3 -5 -2 3 v6 2 1 1 -1