【正文】 =8 λ = v4 T =+∞ T =11 T =+∞ 5 P = T =10 λ = v2 T =11 T =11 T =+∞ 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） T=10 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 9） 例 314（續(xù)） 修改 v6的 T標(biāo)號 ? ? ? ? ? ?? ? ? ? 113856566 ??????? ，舊新 m i nwvPvTm i nvT68 序號 v1 v2 v3 v4 v5 v6 v7 v8 4 T =10 P = T =8 λ = v4 T =+∞ T =11 T =+∞ 5 P = T =10 λ = v2 T =11 T =11 T =+∞ 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 10） 例 314（續(xù)） T=10 ? ? ? ? ? ?? ? ? ? 107323233 ??????? ，舊新 m i nwvPvTm i nvT將 v3改 P標(biāo)號并標(biāo)路徑 69 序號 v1 v2 v3 v4 v5 v6 v7 v8 4 T =10 P = T =8 λ = v4 T =+∞ T =11 T =+∞ 5 P = T =10 λ = v2 T =11 T =11 T =+∞ 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 T=11 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 11） 例 314（續(xù)） 修改 v8的 T標(biāo)號 ? ? ? ? ? ?? ? ? ? 1661038388 ??????? ，舊新 m i nwvPvTm i nvT70 序號 v1 v2 v3 v4 v5 v6 v7 v8 4 T =10 P = T =8 λ = v4 T =+∞ T =11 T =+∞ 5 P = T =10 λ = v2 T =11 T =11 T =+∞ 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 12） 例 314（續(xù)） T=11 將 v6或 v7改 P標(biāo)號并標(biāo)路徑 ? ? ? ? ? ?? ? ? ? 113856566 ??????? ，舊新 m i nwvPvTm i nvT71 序號 v1 v2 v3 v4 v5 v6 v7 v8 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 T=11 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 13） 例 314（續(xù)） 修改 v7， v8的 T標(biāo)號 ? ? ? ? ? ?? ? ? ? 111111167677 ????? ，舊新 m i nwvPvTm i nvT? ? ? ? ? ?? ? ? ? 132111668688 ????? ，舊新 m i nwvPvTm i nvT注意仍使用原路徑 72 序號 v1 v2 v3 v4 v5 v6 v7 v8 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 14） 例 314（續(xù)） 注意仍使用原路徑 T=11 將 v7改 P標(biāo)號并標(biāo)路徑 ? ? ? ? ? ?? ? ? ? 114747477 ??????? ，舊新 m i nwvPvTm i nvT73 序號 v1 v2 v3 v4 v5 v6 v7 v8 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 T=13 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 15） 例 314（續(xù)） 兩種情況均考慮 修改 v8的 T標(biāo)號 ? ? ? ? ? ?? ? ? ? 132111378788 ????? ，舊新 m i nwvPvTm i nvT74 序號 v1 v2 v3 v4 v5 v6 v7 v8 6 P = T =11 λ = v5 T =11 T =16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 T=13 167。 4 最短路問題 二、最短路算法 例 314（續(xù)） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 16） 例 314（結(jié)果） 兩種情況均考慮 P=11 將 v8改 P標(biāo)號并標(biāo)路徑 ? ? ? ? ? ?? ? ? ? 132111378788 ????? ，舊新 m i nwvPvTm i nvT? ? ? ? ? ?? ? ? ? 132111668688 ????? ，舊新 m i nwvPvTm i nvT75 序號 v1 v2 v3 v4 v5 v6 v7 v8 1 P =0 T =+∞ T =+∞ T =+∞ T =+∞ T =+∞ T =+∞ T =+∞ 2 P = T =3 λ = v1 T =+∞ T =7 T =+∞ T =+∞ T =+∞ T =+∞ 3 T =10 P = T =7 λ = v1 T =9 T =+∞ T =+∞ T =+∞ 4 T =10 P = T =8 λ = v4 T =+∞ T =11 T =+∞ 5 P = T =10 λ = v2 T =11 T =11 T =+∞ 6 P = T =11 λ = v5 T =11 T = 16 7 P = T =11 λ = v4 T =13 8 P = T =13 λ = v6 或 v7 167。 4 最短路問題 二、最短路算法 例 314（結(jié)果） 例 314（續(xù)） （ 17） 例 314（結(jié)論） 結(jié)果 （全表） ： 76 由始點 1v 到終點 8v 的最短路的總權(quán)值為 ? ? 1318 ?*W ? ； 由始點 1v 到終點8v的最短路有兩條： ? ?874118 vvvv* ，，??或 ? ?86541 vvvvv ，， 由 1v 到任何一點的最短路及其總權(quán)值，如由 1v 到 3v 的最短路為： ? ?32113 vvv* ，?? ，總權(quán)值為 ? ? 1013 ?*W ? 。 167。 4 最短路問題 二、最短路算法 例 314（結(jié)果） 例 314（續(xù)） v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 （ 18） 例 315 結(jié)論： ● ● ● 返回上頁查看 返回上頁查看 返回上頁查看 需要指出的是， Dijkstra算法只適用于所有弧的權(quán)值為非負(fù)的情況，若存在權(quán)值為負(fù)的弧，則算法失效，下面通過一個簡單的例子來說明這一點。 77 167。 4 最短路問題 二、最短路算法 例 314（結(jié)果） 例 315 第四章 網(wǎng)絡(luò)計劃技術(shù) Dijkstra算法求解表 2. 圖中存在含負(fù)權(quán)弧時最短路的求解算法 。（自學(xué)） 說明能否用 Dijkstra算法計算右圖 v1到 v2的最短路。 v1 v2 v3 3 2 1 解 序號 v 1 v 2 v 3 1 P =0 T =+∞ T =+∞ 2 P = T =1 λ = v 1 T =2 3 P = T =2 λ = v 1 Dijkstra算法得到的最短路： 真正最短路： ? ?2112 vv* ，?? 112 ?*W? ?23112 vvv* ，?? 112 ??*W78 謝謝！請看下一章