第五章圖(四)

1、第七講 圖浙江大學 陳 越6.6 最短路徑問題 若用帶權圖表示交通網，圖中頂點表示地點，邊代表兩地之間有直接道路，邊上的權值表示路程(或所花費用或時間) 。從一個地方到另一個地方的路徑長度表示該路徑上各邊的權值之和。問題： 兩地之間是否有通路? 在有多條通路的情況下，哪條最短? 考慮到交通網的有向性，直接討論的是帶權有向圖的最短路徑問題，但解決問題的算法也適用于無向圖。 將一個路徑的起始頂點稱為源點，最后一個頂點稱為終點。問題分類單源最短路徑問題：從某固定源點出發(fā)，求其到所有其他頂點的最短路徑（有向）無權圖（有向）有權圖多源最短路徑問題：求任意兩頂點間的最短路徑6.6.1無權圖的單源最短路算法

2、按照遞增（非遞減）的順序找出固定頂點到各個頂點的最短路.Dijkstra算法（迪杰斯特拉）1.無權圖的單源最短路算法0 v31 v1v42v2 2v5 30: 1: 2: v3v1 and v6v2 and v41 v6v7 33: v5 and v7在無權圖中，經過頂點最少的路就是最短路。2.有權圖的單源最短路算法從v1出發(fā)到v6的最短路徑是：權重和最小的按照遞增的順序找出到各個頂點的最短路課本例題6.17用Dijkstra網圖6.30中v0到所有其余頂點的最短路徑。這是一個按距離遞增的順序逐步找出v0到所有其余頂點的最短路徑的過程.D 表示存儲v0到其余頂點的“當前最短距離”P 對應的最短

3、路徑鄰接于哪那個頂點初始時（第0步），數(shù)組D就是該圖鄰接矩陣表示時v0對應的行向量在D中選擇到v0距離最小的頂點v1，可以斷定，頂點v1已經找到了到v0的最短距離。因此， v1作為已經求得最短路徑的頂點，通過繞行v1 ， v0到其余頂點的當前最短距離很可能更短。選v1 （第1步），考慮v1的鄰接點v2和 v3（不需考慮已經求得最短距離的v0 ，D1用灰色表示，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v3 ，通過繞行v3 ， v0到其余頂點的當前最短距離很可能更短。選v3 （第2步），考慮v3的鄰接點v5和 v6（不需考慮已經求得最短距離的v1和 v3 ，D1和D

4、3用灰色表示，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v6 ，通過繞行， v0到其余頂點的當前最短距離很可能更短。選v6 （第3步），考慮v6的鄰接點v5和 v8（不需考慮已經求得最短距離的v0和 v1 、 v3 、 v6 ，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v2 ，通過繞行， v0到其余頂點的當前最短距離很可能更短。選v2 （第4步），考慮v2的鄰接點v5和 v4（不需考慮已經求得最短距離的v0和 v1 、 v3 、 v6 、 v2 ，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v5 ，通過繞行

5、， v0到其余頂點的當前最短距離很可能更短。選v5 （第5步），考慮v5的鄰接點v4、 v8和 v7（不需考慮已經求得最短距離的v0和 v1 、 v3 、 v6 、 v2 、 v5 ，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v4 ，通過繞行， v0到其余頂點的當前最短距離很可能更短。選v4 （第6步），考慮v4的鄰接點 v7（不需考慮已經求得最短距離的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 ，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v8 ，通過繞行， v0到其余頂點的當前最短距離很可能更短。選v8 （第7步

6、），考慮v8的鄰接點 v7和v9 （不需考慮已經求得最短距離的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 、 v8 ，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v7 ，通過繞行， v0到其余頂點的當前最短距離很可能更短。選v7 （第8步），考慮v7的鄰接點 v9 （不需考慮已經求得最短距離的v0和 v1 、 v3 、 v6 、 v2 、 v5 、 v4 、 v8 、 v7 ，不參與下一步最短路徑的選擇） 因此，在數(shù)組D中選擇到 v0距離最小的頂點v9 。選v9 （第9步）。（不需考慮已經求得最短距離的v0和 v1 、 v3 、 v6 、 v2

7、、 v5 、 v4 、 v8 、 v7 ，不參與下一步最短路徑的選擇） D1-D9表示從v0到v1-v9 的最短距離。通過搜索數(shù)組P得到最短路徑，比如，v0到v9的最短路徑可以這樣得到：P9=7，P7=4，P4=5，P5=3，P3=1，P1=0，順序到過來就是：v0，v1，v3 ，v5，v4，v7，v9.Dijkstra 算法令S=源點s + 已經確定了最短路徑的頂點vi對任一未收錄的頂點v，定義distv為s到v的最短路徑長度，但該路徑僅經過S中收集的頂點。即路徑s(viS)v的最小長度若路徑是按照遞增（非遞減）的順序生成的，則真正的最短路必須只經過S中的頂點。每次從未收錄的頂點中選一個di

8、st最小的收錄增加一個v進入S，可能影響另外一個w的dist值?。╲一定是s到w的路徑上，v一定與w有一條直接的邊）distw = mindistw, distv + 的權重的權重6.6.2多源最短路算法方法1：直接將單源最短路算法調用|V|遍T = O( |V|3 + |E|V|)方法2：T = O( |V|3 )對于稀疏圖效果好算法對于稠密圖效果好課本例題6.19用Floyd網圖6.31中每一對頂點之間的最短路徑。 帶權有向圖及其帶權有向圖及其鄰接鄰接矩陣矩陣 0 6 114 0 2 3 0V12116V2V034最后得到的每對頂點之間的最短路徑長度及其最短路徑都應該分別是一個二維矩陣，分

9、別用二維數(shù)組D和二維數(shù)組P表示。Dij表示從vi到vj的最短路徑長度，Pij表示從vi到vj的最短路徑上vj的父頂點號。第一步 查看v0：0行0列以外的非對角元素，D12=2垂直和水平方向分別向0列0行投影兩個元素之和D10+D02=4+11=15，因為152，所以D12=2保持不變。D21=，垂直和水平方向分別向0列0行投影兩個元素之和D01+D20=3+6=9，因為93，所以D20=3保持不變。D02=11，垂直和水平方向分別向1列1行投影兩個元素之和D01+D12=6+2=8，因為86，所以D01=6保持不變。D10=4，垂直和水平方向分別向2列2行投影兩個元素之和D12+D20=2+3

10、=5，因為45,保持不變。下面考察最短路徑矩陣P，與D的演變過程相對應：Pij=i的含義是：從vi到vj的最短路徑中，vj的前驅結點（父結點）為vi，即初始假設直接的邊就是最短路徑。102100112多源最短路算法Floyd 算法Dkij = 路徑 i l k j 的最小長度的最小長度D0, D1, , D|V|-1ij即給出了即給出了i到到j的真正最短距離的真正最短距離最初的D-1是什么？當Dk-1已經完成，遞推到Dk時：或者k 最短路徑 i l k j ，則，則Dk = Dk-1或者k 最短路徑 i l k j ，則該路徑必定由兩，則該路徑必定由兩段最短路徑組成： Dkij=Dk1ik+D

11、k1kj0123452030606515201080403570圖圖 帶權有向圖及其帶權有向圖及其鄰接鄰接矩陣矩陣 20 60 10 65 30 70 40 35 20 15 80 表表 求最短路徑時數(shù)組求最短路徑時數(shù)組dist和和pre的各分量的變化情況的各分量的變化情況 初始化為Pathij=-1，表示從Vi到Vj 不經過任何(S中的中間)頂點。當某個頂點Vk加入到S中后使Aij變小時，令Pathij=k。 下表給出了利用Floyd算法求圖的帶權有向圖的任意一對頂點間最短路徑的過程。圖圖 帶權有向圖及其帶權有向圖及其鄰接鄰接矩陣矩陣 0 2 8 0 4 5 0V1482V2V05 表表 用用Floyd算法求任意一對頂點間算法求任意一對頂點間最短路徑最短路徑 0 2 8 0 45 0 0 2 8 0 4 5 7 0 0 2 6 0 4 5 7 0 0 2 6 9 0 4 5 7 0A -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 -1 -1 -1 -1 0 -1 -1 -1 1 2 -1 -1 -1 0 -1PathS 0 0, 1 0, 1, 2 步驟步驟初態(tài)初態(tài)k=0K=1K=2根據上述