最短路問題（課堂PPT）

1、賦權(quán)圖賦權(quán)圖v給定賦權(quán)圖的一個子圖給定賦權(quán)圖的一個子圖H，定義，定義H的權(quán)為的權(quán)為H的所有邊權(quán)的總和。的所有邊權(quán)的總和。最短路問題最短路問題n對圖對圖G的每條邊的每條邊e，賦予一實數(shù)，賦予一實數(shù)(e)，稱為邊，稱為邊e的權(quán)，可得一的權(quán)，可得一賦權(quán)圖。賦權(quán)圖。UDBVCEA712244731555v賦權(quán)圖中一條路的權(quán)稱為路長。賦權(quán)圖中一條路的權(quán)稱為路長。n在一個賦權(quán)圖在一個賦權(quán)圖G上，給定兩個頂點上，給定兩個頂點u和和 v，所謂，所謂u和和 v最短最短 路是指所有連接頂點路是指所有連接頂點u和和 v 的路中路長最短的路；的路中路長最短的路；nu和和 v最短路的路長也稱為最短路的路長也稱為u和和

2、v的距離。的距離。UDBVCEA227414731555vDijkstra算法的基本思想：算法的基本思想：),(),(),(00vuwuuduud,),(),(min),(00SvSuvuwuudSud(1)uvu0u1SPPSVSSu ,0設設S是是V的真子集，的真子集，vuuP0S如果是從如果是從u 0 到到 的最短路，的最短路，Su),(0uu),(0uu則則 ，并且，并且P的的 段是最短的段是最短的路，所以路，所以算法標號算法標號v令令l ij表示從頂點表示從頂點vi到頂點到頂點vj的距離；的距離； dij表示連接頂點表示連接頂點vi與頂點與頂點vj邊上的權(quán)，即邊上的權(quán)，即)(,)(,

3、GEvvGEvvwdjijiijij公式（公式（1）是）是Dijkstra算法的基礎。算法的基礎。算法以標號方式進行，每進行一次都增加一個標號點，算法以標號方式進行，每進行一次都增加一個標號點，直至找到所求的最短路。直至找到所求的最短路。,),(),(min),(00SvSuvuwuudSud(1)Dijkstra算法步驟算法步驟vStep0 在點在點vs上標號上標號lss=0；,minSvSvdlljiijsisk,kkvSSvSSnStep4 lst是所求的最短路長，反向追蹤找出是所求的最短路長，反向追蹤找出所求所求vs- vt最短路最短路.nStep3 令令SnStep2 令令S表示所有

4、已標號點，表示所有已標號點， 表示未標號點，表示未標號點， 計算計算lsj ，轉(zhuǎn)，轉(zhuǎn)Step3nStep1 若若vt已標號，轉(zhuǎn)已標號，轉(zhuǎn)Step4； 否則轉(zhuǎn)否則轉(zhuǎn)Step2；計算實例計算實例求連接求連接S、V的最短路的最短路SDBVCEA227414731555SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，sSDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，sSDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，ASDBVCEA227414731555

5、02，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，BSDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，ESDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，DLUV = 13;S-V最短路為最短路為SABEDVSDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，

6、D13，D實例評述實例評述vDijkstra算法不僅找到了所求最短路，而且找到了從算法不僅找到了所求最短路，而且找到了從S點到其他所有頂點的最短路；這些最短路構(gòu)成了圖的點到其他所有頂點的最短路；這些最短路構(gòu)成了圖的一個連通無圈的支撐子圖，即圖的一個支撐樹。一個連通無圈的支撐子圖，即圖的一個支撐樹。SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，DvDijkstra算法也適用于有向賦權(quán)圖算法也適用于有向賦權(quán)圖.SDBVCEA712244731555選址問題選址問題v設設G表示一個礦區(qū)的

7、交通運輸圖，礦井和之間的里程是；表示一個礦區(qū)的交通運輸圖，礦井和之間的里程是；現(xiàn)在需建一個礦區(qū)煤炭運輸站，把運輸站設在哪個礦井所在地現(xiàn)在需建一個礦區(qū)煤炭運輸站，把運輸站設在哪個礦井所在地才能使得離運輸站距離最遠的礦井可運輸里程最短。這就是最才能使得離運輸站距離最遠的礦井可運輸里程最短。這就是最簡單的選址問題。簡單的選址問題。v礦區(qū)的交通運輸圖是一個賦權(quán)圖，每個礦井是圖的一個頂點。礦區(qū)的交通運輸圖是一個賦權(quán)圖，每個礦井是圖的一個頂點。v在賦權(quán)圖在賦權(quán)圖G中，定義頂點中，定義頂點u的離距為：的離距為：ivjvijc),(max)(uVvvudud中心問題中心問題網(wǎng)絡網(wǎng)絡G的一個中心是滿足下列條件的

8、的一個中心是滿足下列條件的G的頂點的頂點u選址問題可化為求選址問題可化為求G的中心問題。的中心問題。求圖的中心的算法過程：求圖的中心的算法過程：用用Dijkstra算法求出算法求出G的任意兩點間的距離；的任意兩點間的距離；求出每點的離距求出每點的離距d(v)求滿足（求滿足（2）的頂點）的頂點v即是中心即是中心),(min)(Vvvdud（2）實例實例圖圖7-15給出了一個礦區(qū)的交通運輸圖。應把運輸站建給出了一個礦區(qū)的交通運輸圖。應把運輸站建在哪個礦井才能滿足選址要求？在哪個礦井才能滿足選址要求？v3v4v5v2v6v1v763221.531.81.52.5v這個問題實際上只需求出這個問題實際上

9、只需求出G的一個中心即可。按上面的算的一個中心即可。按上面的算法過程，首先利用法過程，首先利用Dijkstra算法得到圖算法得到圖7-15的距離表；再的距離表；再求出每個點的離距，最后找出離距的最小者求出每個點的離距，最后找出離距的最小者v 6就是建運就是建運輸站的礦井。輸站的礦井。3 . 605 . 13 . 63 . 34368 . 45 . 108 . 48 . 15 . 25 . 15 . 43 . 63 . 38 . 13023 . 63 . 93 . 63 . 38 . 13023 . 33 . 6545 . 2520253 . 635 . 13 . 63 . 32033 . 96

10、5 . 43 . 93 . 6530)(76543217654321vvvvvvvvdvvvvvvvi4.8v*=注注:Dijkstra算法只適用于所有算法只適用于所有ij0的情形，當賦的情形，當賦權(quán)有向圖中存在負權(quán)時，算法失效。如權(quán)有向圖中存在負權(quán)時，算法失效。如v1v2v3 12-3用用Dijkstra算法可以得出從算法可以得出從1到到v2的最短路的權(quán)是的最短路的權(quán)是1，但實際，但實際上從上從1到到v2的最短路是（的最短路是（1， v3 ，v2），權(quán)是），權(quán)是-1。下面介紹具有負權(quán)賦權(quán)有向圖下面介紹具有負權(quán)賦權(quán)有向圖D的最短路的算法。的最短路的算法。不妨假設從任一點不妨假設從任一點vi到任

11、一點到任一點vj都有一條?。ㄈ绻诙加幸粭l弧（如果在D中，中，（ vi，vj ） A，則添加?。?，則添加?。?vi，vj ）令）令wij=+ ）。）。顯然，從顯然，從vs到任一點到任一點vj的最短路總是從的最短路總是從vs出發(fā)到某個點出發(fā)到某個點vi，再沿（再沿（vi，vj）到）到vj的，由前面的結(jié)論可知，從的，由前面的結(jié)論可知，從vs到到vi的的這條路必定是從這條路必定是從vs到到vi的最短路，所以的最短路，所以d（vs，vj）必滿）必滿足如下方程：足如下方程：ijisijswvvdvvd),(),(minijisijswvvdvvd),(),(min可用如下遞推公式：為了求得這個方程的解),(,),(),(21nsssvvdvvdvvd），（令）（njwvvdsjjs21),(1), 2 , 1(),(),(321minnjwvvdvvdtijistijst）（）（，對有，步時，對所有第若進行到某一步，例如njk21),(),(1jskjskvvdvvd）（）（到各點的最短路的權(quán)。）既為，（則）（sjskvnjvvd21),(1v2v3v4v5v6v7v8v6-1-3-283-52-111-1217-3-5例：求例：求1到各點的最短路到各點的最