最短路問題課件

賦權圖給定賦權圖的一個子圖H，定義H的權為H的所有邊權的總和。最短路問題對圖G的每條邊e，賦予一實數ω(e)，稱為邊e的權，可得一賦權圖。UDBVCEA7122447315551賦權圖給定賦權圖的一個子圖H，定義H的權為H的所有邊權的總和賦權圖中一條路的權稱為路長。在一個賦權圖G上，給定兩個頂點u和v，所謂u和

v最短路是指所有連接頂點u和v

的路中路長最短的路；u和v最短路的路長也稱為u和v的距離。UDBVCEA2274147315552賦權圖中一條路的權稱為路長。在一個賦權圖G上，給定兩個頂點uDijkstra算法的基本思想：(1)u0u1P設S是V的真子集，如果是從u

0到的最短路，則，并且P的段是最短的路，所以3Dijkstra算法的基本思想：(1)u0u1P設S是V的真算法標號令lij表示從頂點vi到頂點vj的距離；dij表示連接頂點vi與頂點vj邊上的權，即公式（1）是Dijkstra算法的基礎。算法以標號方式進行，每進行一次都增加一個標號點，直至找到所求的最短路。(1)4算法標號令lij表示從頂點vi到頂點vj的距離；dij表Dijkstra算法步驟Step0在點vs上標號lss=0；Step4lst是所求的最短路長，反向追蹤找出所求vs-vt最短路.Step3令Step2令S表示所有已標號點，表示未標號點，計算lsj

，轉Step3Step1若vt已標號，轉Step4；否則轉Step2；5Dijkstra算法步驟Step0在點vs上標號lss=計算實例求連接S、V的最短路SDBVCEA2274147315556計算實例求連接S、V的最短路SDBVCEA227414731SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s7SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A9SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B10SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E11SDBVCEA22741473155502，s5，s4，s∞SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D12SDBVCEA22741473155502，s5，s4，s∞LUV

=13;S-V最短路為SABEDVSDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D13LUV=13;S-V最短路為SABEDVSDBVCEA2實例評述Dijkstra算法不僅找到了所求最短路，而且找到了從S點到其他所有頂點的最短路；這些最短路構成了圖的一個連通無圈的支撐子圖，即圖的一個支撐樹。SDBVCEA22741473155502，s5，s4，s∞，s∞，s∞，s02，s2，s9，A4，A4，s8，C4，A7，B7，B8，E14，E8，E13，D13，D14實例評述Dijkstra算法不僅找到了所求最短路，而且找到了Dijkstra算法也適用于有向賦權圖.SDBVCEA71224473155515Dijkstra算法也適用于有向賦權圖.SDBVCEA712選址問題設G表示一個礦區(qū)的交通運輸圖，礦井和之間的里程是；現在需建一個礦區(qū)煤炭運輸站，把運輸站設在哪個礦井所在地才能使得離運輸站距離最遠的礦井可運輸里程最短。這就是最簡單的選址問題。礦區(qū)的交通運輸圖是一個賦權圖，每個礦井是圖的一個頂點。在賦權圖G中，定義頂點u的離距為：16選址問題設G表示一個礦區(qū)的交通運輸圖，礦井和之間的里程是中心問題網絡G的一個中心是滿足下列條件的G的頂點u選址問題可化為求G的中心問題。求圖的中心的算法過程：用Dijkstra算法求出G的任意兩點間的距離；求出每點的離距d(v)求滿足（2）的頂點v即是中心（2）17中心問題網絡G的一個中心是滿足下列條件的G的頂點u（2）17實例圖7-15給出了一個礦區(qū)的交通運輸圖。應把運輸站建在哪個礦井才能滿足選址要求？v3v4v5v2v6v1v763221.531.81.52.518實例圖7-15給出了一個礦區(qū)的交通運輸圖。應把運輸站建在哪個這個問題實際上只需求出G的一個中心即可。按上面的算法過程，首先利用Dijkstra算法得到圖7-15的距離表；再求出每個點的離距，最后找出離距的最小者v6就是建運輸站的礦井。4.8v*=19這個問題實際上只需求出G的一個中心即可。按上面的算法過程，首注:Dijkstra算法只適用于所有ｗij≥0的情形，當賦權有向圖中存在負權時，算法失效。如v1v2v312-3用Dijkstra算法可以得出從ｖ1到v2的最短路的權是1，但實際上從ｖ1到v2的最短路是（ｖ1，v3

，v2），權是-1。20注:Dijkstra算法只適用于所有ｗij≥0的情形，當賦權下面介紹具有負權賦權有向圖D的最短路的算法。不妨假設從任一點vi到任一點vj都有一條?。ㄈ绻贒中，（vi，vj

）A，則添加?。╲i，vj

）令wij=+∞）。顯然，從vs到任一點vj的最短路總是從vs出發(fā)到某個點vi，再沿（vi，vj）到vj的，由前面的結論可知，從vs到vi的這條路必定是從vs到vi的最短路，所以d（vs，vj）必滿足如下方程：21下面介紹具有負權賦權有向圖D的最短路的算法。不妨假設從任一點22226-1-3-283-52-111-1217-3-5例：求ｖ1到各點的最短路236-1-3-283-52-111-1217-3-5例：求ｖ1wijv1v2v3v4v5