最短路問題課件

1、關(guān)于最短路問題第一張，PPT共二十四頁，創(chuàng)作于2022年6月1賦權(quán)圖中一條路的權(quán)稱為路長。在一個賦權(quán)圖G上，給定兩個頂點(diǎn)u和 v，所謂u和 v最短 路是指所有連接頂點(diǎn)u和 v 的路中路長最短的路；u和 v最短路的路長也稱為u和 v的距離。UDBVCEA227414731555第二張，PPT共二十四頁，創(chuàng)作于2022年6月Dijkstra算法的基本思想：(1)u0u1P設(shè)S是V的真子集，如果是從u 0 到 的最短路，則 ，并且P的 段是最短的路，所以第三張，PPT共二十四頁，創(chuàng)作于2022年6月算法標(biāo)號令l ij表示從頂點(diǎn)vi到頂點(diǎn)vj的距離； dij表示連接頂點(diǎn)vi與頂點(diǎn)vj邊上的權(quán)，即公式（

2、1）是Dijkstra算法的基礎(chǔ)。算法以標(biāo)號方式進(jìn)行，每進(jìn)行一次都增加一個標(biāo)號點(diǎn)，直至找到所求的最短路。(1)第四張，PPT共二十四頁，創(chuàng)作于2022年6月Dijkstra算法步驟Step0 在點(diǎn)vs上標(biāo)號lss=0；Step4 lst是所求的最短路長，反向追蹤找出所求vs- vt最短路.Step3 令Step2 令S表示所有已標(biāo)號點(diǎn)， 表示未標(biāo)號點(diǎn)， 計算lsj ，轉(zhuǎn)Step3Step1 若vt已標(biāo)號，轉(zhuǎn)Step4； 否則轉(zhuǎn)Step2；第五張，PPT共二十四頁，創(chuàng)作于2022年6月計算實(shí)例求連接S、V的最短路SDBVCEA227414731555第六張，PPT共二十四頁，創(chuàng)作于2022年6月

3、SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s第七張，PPT共二十四頁，創(chuàng)作于2022年6月SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s第八張，PPT共二十四頁，創(chuàng)作于2022年6月SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A第九張，PPT共二十四頁，創(chuàng)作于2022年6月SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B第十張，PPT共二十四頁，創(chuàng)作于20

4、22年6月SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E第十一張，PPT共二十四頁，創(chuàng)作于2022年6月SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D第十二張，PPT共二十四頁，創(chuàng)作于2022年6月LUV = 13;S-V最短路為SABEDVSDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8

5、，E13，D13，D第十三張，PPT共二十四頁，創(chuàng)作于2022年6月實(shí)例評述Dijkstra算法不僅找到了所求最短路，而且找到了從S點(diǎn)到其他所有頂點(diǎn)的最短路；這些最短路構(gòu)成了圖的一個連通無圈的支撐子圖，即圖的一個支撐樹。SDBVCEA22741473155502，s5，s4，s，s，s，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D第十四張，PPT共二十四頁，創(chuàng)作于2022年6月Dijkstra算法也適用于有向賦權(quán)圖.SDBVCEA712244731555第十五張，PPT共二十四頁，創(chuàng)作于2022年6月選址問題設(shè)G表示一個礦區(qū)的交通運(yùn)輸圖，礦井和

6、之間的里程是；現(xiàn)在需建一個礦區(qū)煤炭運(yùn)輸站，把運(yùn)輸站設(shè)在哪個礦井所在地才能使得離運(yùn)輸站距離最遠(yuǎn)的礦井可運(yùn)輸里程最短。這就是最簡單的選址問題。礦區(qū)的交通運(yùn)輸圖是一個賦權(quán)圖，每個礦井是圖的一個頂點(diǎn)。在賦權(quán)圖G中，定義頂點(diǎn)u的離距為：第十六張，PPT共二十四頁，創(chuàng)作于2022年6月中心問題網(wǎng)絡(luò)G的一個中心是滿足下列條件的G的頂點(diǎn)u選址問題可化為求G的中心問題。求圖的中心的算法過程：用Dijkstra算法求出G的任意兩點(diǎn)間的距離；求出每點(diǎn)的離距d(v)求滿足（2）的頂點(diǎn)v即是中心（2）第十七張，PPT共二十四頁，創(chuàng)作于2022年6月實(shí)例圖7-15給出了一個礦區(qū)的交通運(yùn)輸圖。應(yīng)把運(yùn)輸站建在哪個礦井才能滿足

7、選址要求？v3v4v5v2v6v1v763221.531.81.52.5第十八張，PPT共二十四頁，創(chuàng)作于2022年6月這個問題實(shí)際上只需求出G的一個中心即可。按上面的算法過程，首先利用Dijkstra算法得到圖7-15的距離表；再求出每個點(diǎn)的離距，最后找出離距的最小者v 6就是建運(yùn)輸站的礦井。4.8v*=第十九張，PPT共二十四頁，創(chuàng)作于2022年6月注:Dijkstra算法只適用于所有ij0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時，算法失效。如v1v2v3 12-3用Dijkstra算法可以得出從1到v2的最短路的權(quán)是1，但實(shí)際上從1到v2的最短路是（1， v3 ，v2），權(quán)是-1。第二十張，PPT共二十四頁，創(chuàng)作于2022年6月下面介紹具有負(fù)權(quán)賦權(quán)有向圖D的最短路的算法。不妨假設(shè)從任一點(diǎn)vi到任一點(diǎn)vj都有一條弧（如果在D中，（ vi，vj ） A，則添加?。?vi，vj ）令wij=+ ）。顯然，從vs到任一點(diǎn)vj的最短路總是從vs出發(fā)到某個點(diǎn)vi，再沿（vi，vj）到vj的，由前面的結(jié)論可知，從vs到vi的這條路必定是從vs到vi的最短路，所以d（vs，vj）必滿足如下方程：第二十一張，PPT共二十四頁，創(chuàng)作于2022年6月第二十二