运筹学_最短路问题.pptVIP

§3 最短路问题 例3 用Dijkstra 算法 例9 用Dijkstra 算法 P158 类例4 P158 类例4 P158 类例4求图中任意两点间的最短路。 P158 类例4求图中任意两点间的最短路。 P158 类例4 例13_D 求v1到v8的最短路路径 求v1到v8的最短路路径 忠实算法 例11 * 试探性标号(tentative label), 永久性标号(permanent label) T (v j) = min [T (v j), P (v i) + l i j ] ⑶ 比较所有具有T标号的点, 最小者改为P标号。 Dijkstra 算法(不含负权边) ⑴ 给vi 以P标号, P( vi )=0 , 其余各点均给T标号, T (vi)=+∞ ⑵ 与刚获P标号点vi 以相邻只有T 标号各点v j 改进： P (v i) = min [T (v j) ] 并列最小者, 同时改为P标号。 若全部点均为P标号则停；否则用 v i 代 v i , 转 ⑵ . 求v1点到v7点的最短路。 0 v5 7 4 6 1 6 7 v4 v7 v2 v6 5 2 2 3 v3 v1 2 2 5 6 7 10 0 v5 7 4 6 1 6 7 v4 v7 v2 v6 5 2 2 3 v3 v1 2 2 0 v5 7 4 6 1 6 7 v4 v7 v2 v6 5 2 2 3 v3 v1 2 5 2 0 v5 7 4 6 1 6 7 v4 v7 v2 v6 5 2 2 3 v3 v1 2 6 5 2 0 v5 7 4 6 1 6 7 v4 v7 v2 v6 5 2 2 3 v3 v1 2 7 6 5 2 0 v5 7 4 6 1 6 7 v4 v7 v2 v6 5 2 2 3 v3 v1 2 v1 7 7 ⑴ P(v1)=0, 余皆为T标号:T (vi)=+∞ ( i = 2,…,8 ) 求v1点到v8点的最短路。 ⑵ T(v2)=min(T(v2), P(v1)+l12)=min(+∞,0+4)=4 T(v3)=min(T(v2), P(v1)+l13)=min(+∞,0+6)=6 ⑶P(v2)=4, (v1, v2) ⑸P(v3)=6, (v1, v3) ⑷ T(v4)=min(T(v4), P(v2)+l24) =min(+∞,4+5)=9 T(v5)=min(T(v5), P(v2)+l25) =min(+∞,4+4)=8 ⑹T(v4)=min(T(v4), p(v3)+l34)=min(6,6+4)=9, T(v5)=min(T(v5), P(v3)+l35)=min(8,6+7)=8 v5 7 4 6 1 6 7 v4 v7 v2 v6 5 2 2 3 v3 v1 2 求图中任意两点间的最短路。 dij为两相邻点的距离， 是从 i 到 j 点的直接距离。 D(0) = 5 0 2 2 ∞ 5 0 0 3 ∞ 6 2 4 ∞ 4 1 10 4 2 2 0 2 8 ∞ 0 2 10 1 5 8 v4 4 2 2 6 v2 v5 v1 4 2 3 v3 所以我们先考虑与之间有一个中间点的情况. 从 i 到 j 点的最短距离不一定是 i→ j, i→ l → k→ j, 可能是i→ l → j, n个点的网络, i 到j 的最短距离经过的中间点最多有n-2个 或 i→ l → …→ k→ j, 求图中任意两点间的最短路。 求v1→v2的最短距离为, 具体操作是把第i行和转置后的第j列相加,从中找出最小者. D(0) = 5 0 2 2 ∞ 5 0 0 3 ∞ 6 2 4 ∞ 4 1 10 4 2 2 0 2 8 ∞ 0 2 10 1 5 8 v4 4 2 2 6 v2 v5 v1 4 2 3 v3 所以我们先考虑 i 与 j 之间有一个中间点的情况 min{ d11+d12, d12+d22, d13+d32, d14+d42, d15+d52 } r 应经过网络的每一点,或网络中的每一点都要作中间点. 即 min { d i r + d r 2 } r = 1, 2, …, n 5 5 ∞ 4 ∞ 0 5 1 2 ∞ 5 0 3 ∞ 2 d12(1) = 4 第一行 转置后的第二列 0 5 1 ∞ 2 0 5 2 ∞ 2 0 10 3 ∞ 4 0 5 1 ∞ 2 5 0 3 2 ∞ 5 5 4 ∞ ∞ 0 5 1 ∞ 2 1 10 0