最短路徑問題課件

最短路徑問題

(ShortestPathProblem)1最短路徑問題

(ShortestPathProblem)最短路徑問題所謂最短路徑問題（ShortestPathProblem）就是在一個帶權圖中找出兩點之間的最短路徑（權和最小的路徑）。最短路徑問題通常有如下幾種類型：（1）帶權（非負權）圖中兩個指定點之間的最短路徑；（2）帶權圖（非負權）中任意兩點間的最短路徑；（3）帶權圖（非負權）中從一個指定點到其它所有點的最短路徑；（4）帶權圖（非負權）中必須通過指定點的兩個指定點之間的最短路徑；（5）帶權圖（任意權）中最短路徑問題，等等。2最短路徑問題所謂最短路徑問題（ShortestPa兩個指定點之間的最短路徑問題求解方法一：回溯法(從終點開始逐步逆向推算)主要步驟：先看與終點連接的結點，在結點上方寫上該結點到終點的最短路線及權值；再將每個結點（與終點連接的結點）看成新的終點，以此類推，一直到起點為止。若在這過程中，一個結點同時與多個不同終點相連接，則該結點上方寫上該結點到這些終點中最短的路線及權值；最終，起點上方的最短路線及權值即為起點到終點的最短路線及長度。3兩個指定點之間的最短路徑問題求解方法一：回溯法(從終點開始逐例使用回溯法求下圖中結點1到結點10的最短路徑3006-9-101508-101009-104005-8-102757-8-106002-6-9-105004-6-9-106003-5-8-106501-4-6-9-104例使用回溯法求下圖中結點1到結點10的最短路徑3006-9練習城市A到城市B的交通道路如下圖所示，線上標注的數(shù)字為兩點間距離(單位：萬米)。某公司現(xiàn)需從A市緊急運送一批貨物到B市。假設各條線路的交通狀況相同，請為該公司尋求一條最佳路線。

3

7-B6

8-B8

4-7-B9

5-7-B10

6-8-B161-5-7-B172-5-7-B131-6-8-B18A-1-5-7-B5練習城市A到城市B的交通道路如下圖所示，線上標注的數(shù)字為兩指定點到其它所有點的最短路徑解決這一問題最著名的方法是Dijkstra算法，這個算法是由荷蘭計算機科學教授EdsgerW.Dijkstra在1959年提出的。他在1972年獲得美國計算機協(xié)會授予的圖靈獎，這是計算機科學中最具聲望的獎項之一。6指定點到其它所有點的最短路徑解決這一問題最著名的方法是DijDijkstra算法Dijkstra算法是由近及遠地逐漸找出源點到其它任一點的最短路徑。

假設G=<V,E,W>是一個連通帶權簡單圖，G中頂點為v0,v1,….,vn，假設v0為起點，邊(vi,vj)（或<vi,vj>）的權記為wij，若(vi,vj)（或<vi,vj>）不是圖中的邊，則權為wij=

，標號l(x)表示從v0到x的最短路徑的長度。則Dijkstra算法原理如下：7Dijkstra算法Dijkstra算法是由Dijkstra算法的偽代碼ProcedureDijkstra(G,W,a(,z))beginfori:=1tondol(vi):=l(a):=0S:=;//初始化標號及S，S用于保存已考察過的頂點的序列whileV(G)-S(zS)dobeginu:=不屬于S且l(u)最小的一個頂點；

ifu為頂點zS:=S{u}；

elseS:=S{u}；for所有不屬于S的頂點vdol(v):=min{l(v),l(u)+wuv}；endendDijkstra8Dijkstra算法的偽代碼ProcedureDijkst例

用Dijkstra算法求下圖中從a到所有其它結點的最短路徑及長度。9例用Dijkstra算法求下圖中從a到所有其它結點的最短路步驟uS

abcdez0-01a{a}0422c{a,c}03210123b{a,c,b}0328124d{a,c,b,d}032810145e{a,c,b,d,e}032810136z{a,c,b,d,e,z}03281013l(v):=min{l(v),l(u)+wuv}10步驟uS例

用Dijkstra算法求下圖中從A到其它所有結點的最短路徑及長度11例用Dijkstra算法求下圖中從A到其它所有結點的最短路步驟uS

ABCDEFG0-01A{A}0712C{A,C}041543F{A,C,F}0411454114B{A,C,F,B}0411254115E{A,C,F,B,E}041125476G{A,C,F,B,E,G}04112547可以在Dijkstra算法的基礎之上以如下方法找到最短路徑：從終點往回走，找到它的前導頂點，使得它們之間的標號的差等于連接它們邊的權重，如此下去直至到起點，從而找到一條最短路徑。12步驟uS作業(yè)用Dijkstra算法求出下圖中從頂點a到其它所有頂點的最短路徑及及長度。13作業(yè)用Dijkstra算法求出下圖中從頂點a到其它所有頂點有向圖中求最短路徑的Dijkstra算法設Sj是帶權有向圖G中自頂點1到頂點j的最短有向路的長度步驟1：置P={1}，T={2,3,…,n}且S1=0，Sj=w1j，j=2,3,…,n。步驟2：在T中尋找一點k，使得Sk=min{Sj}，置P=P{k}，T=T-{k}。若T=，終止；否則，轉向步驟3。步驟3：對T中每一點j，置Sj=min{Sj，Sk+wkj}，然后轉向步驟2。算法經(jīng)過n-1次循環(huán)結束。14有向圖中求最短路徑的Dijkstra算法設Sj是帶權有向圖G任意兩點間的最短路徑Floyd算法Warshall算法15任意兩點間的最短路徑Floyd算法15任意兩點間的最短路徑-Floyd算法首先定義兩種矩陣運算：定義1

已知矩陣A=(aij)ml，B=(bij)l

n，規(guī)定C=AB=(cij)mn，其中cij=min(ai1+b1j,ai2+b2j,…,ail+blj)定義2

已知矩陣A=(aij)mn，B=(bij)mn，規(guī)定C=AB=(dij)mn，其中dij=min(aij,bij)16任意兩點間的最短路徑-Floyd算法首先定義兩種矩陣運算：1例已知矩陣W，求WW17例已知矩陣W，求WW17例已知矩陣W，求WWcij=min(ai1+b1j,ai2+b2j,…,ail+blj)18例已知矩陣W，求WWcij=min(ai1+b1j,acij=min(ai1+b1j,ai2+b2j,…,ail+blj)19cij=min(ai1+b1j,ai2+b2j,…,ai任意兩點間的最短路徑-Floyd算法算法原理：若W=(wij)nn是圖G的權矩陣，計算W[2]，W[3]，…，W[n]及S，其中W[k]=W[k-1]W=(wij[k])nn；

S=WW[2]W[3]

…W[n]=(sij)nn

。則wij[k]表示頂點i到頂點j經(jīng)過k條邊且權和最小的路徑，sij表示頂點i到頂點j權和最小的路徑（最短路徑）。20任意兩點間的最短路徑-Floyd算法算法原理：20例求下圖中任意兩點間最短路徑的長度。21例求下圖中任意兩點間最短路徑的長度。212222由s16知，頂點v1到v6的最短路徑為6；由s35知，頂點v3到v5的最短路徑為2；由s45知，頂點v4到v5沒有最短路徑；23由s16知，頂點v1到v6的最短路徑為6；23任意兩點間的最短路徑-Warshall算法算法原理：（1）輸入圖G的權矩陣W；（2）置k:=1；（3）置i:=1；（4）修改矩陣W中的權值，

wij:=min(wij,wik+wkj)，j=1,2,…,n；（5）i:=i+1，若in，轉(4)；（6）k:=k+1，若kn，轉(3)；否則停止。24任意兩點間的最短路徑-Warshall算法算法原理：24例求下圖中任意兩點間最短路徑的長度。wij

:=min(wij,wik+wkj)25例求下圖中任意兩點間最短路徑的長度。wij:=min(wwij:=min(wij,wik+wkj)26wij:=min(wij,wik+wkj)262727Floyd算法的改進Floyd算法和Warshall算法只能給出任意兩點間的最短路徑的長度。改進的Warshall算法不僅能夠給出任意兩點間的最短路徑的長度，同時也給出具體的最短路徑。28Floyd算法的改進Floyd算法和Warsh改進后的Warshall算法算法原理：（1）輸入圖G的權矩陣W=(wij)nn和矩陣P=(pij)nn

，其中pij=i。（2）置k:=1；（3）置i:=1；（4）修改矩陣W和P中的值，

wij:=min(wij,wik+wkj)，j=1,2,…,n；

pij=pkj，j=1,2,…,n；（5）i:=i+1，若in，轉(4)；（6）k:=k+1，若kn，轉(3)；否則停止。矩陣P中pij的值是最短路徑上從i到j被訪問的最后一個頂點，所以利用該矩陣可以重構最短路徑。29改進后的Warshall算法算法原理：矩陣P中pij的值是最帶負權圖中的單源最短路徑問題Dijkstra算法能夠用于求帶負權圖中的指定兩點間的最短路徑？30帶負權圖中的單源最短路徑問題Dijkstra算法能夠用于求帶例求下圖中頂點a到c的最短路徑。如果用Dijkstra算法，則求出的最短路徑為ac，而不是abc。31例求下圖中頂點a到c的最短路徑。如果用Dijkstra算法帶負權圖中的單源最短路徑問題Bellman-Ford算法該算法有一個限制條件，即要求圖中不能包含權和為負值的回路。32帶負權圖中的單源最短路徑問題Bellman-Ford算法32Bellman-Ford算法Bellman-Ford算法的目的是構造一個最短路徑長度數(shù)組序列dist1[v],dist2[v],…,distn-1[v]，其中dist1[v]表示從起點u到圖中其它所有頂點v的只經(jīng)過一條邊的長度，distk[v]表示從起點u到頂點v的最多經(jīng)過k條邊的最短路徑的長度。Bellman-Ford算法最終的目的是算出distn-1[v]。

dist1[v]的生成：dist1[u]=0；若<u,v>是圖中的有向邊，則dist1[v]=wuv，否則dist1[v]=。distk[v]的生成：distk[v]=min{distk-1[v],min{distk-1[j]+wjv}}。33Bellman-Ford算法Bellman-Fo最短路徑問題

(ShortestPathProblem)34最短路徑問題

(ShortestPathProblem)最短路徑問題所謂最短路徑問題（ShortestPathProblem）就是在一個帶權圖中找出兩點之間的最短路徑（權和最小的路徑）。最短路徑問題通常有如下幾種類型：（1）帶權（非負權）圖中兩個指定點之間的最短路徑；（2）帶權圖（非負權）中任意兩點間的最短路徑；（3）帶權圖（非負權）中從一個指定點到其它所有點的最短路徑；（4）帶權圖（非負權）中必須通過指定點的兩個指定點之間的最短路徑；（5）帶權圖（任意權）中最短路徑問題，等等。35最短路徑問題所謂最短路徑問題（ShortestPa兩個指定點之間的最短路徑問題求解方法一：回溯法(從終點開始逐步逆向推算)主要步驟：先看與終點連接的結點，在結點上方寫上該結點到終點的最短路線及權值；再將每個結點（與終點連接的結點）看成新的終點，以此類推，一直到起點為止。若在這過程中，一個結點同時與多個不同終點相連接，則該結點上方寫上該結點到這些終點中最短的路線及權值；最終，起點上方的最短路線及權值即為起點到終點的最短路線及長度。36兩個指定點之間的最短路徑問題求解方法一：回溯法(從終點開始逐例使用回溯法求下圖中結點1到結點10的最短路徑3006-9-101508-101009-104005-8-102757-8-106002-6-9-105004-6-9-106003-5-8-106501-4-6-9-1037例使用回溯法求下圖中結點1到結點10的最短路徑3006-9練習城市A到城市B的交通道路如下圖所示，線上標注的數(shù)字為兩點間距離(單位：萬米)。某公司現(xiàn)需從A市緊急運送一批貨物到B市。假設各條線路的交通狀況相同，請為該公司尋求一條最佳路線。

3

7-B6

8-B8

4-7-B9

5-7-B10

6-8-B161-5-7-B172-5-7-B131-6-8-B18A-1-5-7-B38練習城市A到城市B的交通道路如下圖所示，線上標注的數(shù)字為兩指定點到其它所有點的最短路徑解決這一問題最著名的方法是Dijkstra算法，這個算法是由荷蘭計算機科學教授EdsgerW.Dijkstra在1959年提出的。他在1972年獲得美國計算機協(xié)會授予的圖靈獎，這是計算機科學中最具聲望的獎項之一。39指定點到其它所有點的最短路徑解決這一問題最著名的方法是DijDijkstra算法Dijkstra算法是由近及遠地逐漸找出源點到其它任一點的最短路徑。

假設G=<V,E,W>是一個連通帶權簡單圖，G中頂點為v0,v1,….,vn，假設v0為起點，邊(vi,vj)（或<vi,vj>）的權記為wij，若(vi,vj)（或<vi,vj>）不是圖中的邊，則權為wij=

，標號l(x)表示從v0到x的最短路徑的長度。則Dijkstra算法原理如下：40Dijkstra算法Dijkstra算法是由Dijkstra算法的偽代碼ProcedureDijkstra(G,W,a(,z))beginfori:=1tondol(vi):=l(a):=0S:=;//初始化標號及S，S用于保存已考察過的頂點的序列whileV(G)-S(zS)dobeginu:=不屬于S且l(u)最小的一個頂點；

ifu為頂點zS:=S{u}；

elseS:=S{u}；for所有不屬于S的頂點vdol(v):=min{l(v),l(u)+wuv}；endendDijkstra41Dijkstra算法的偽代碼ProcedureDijkst例

用Dijkstra算法求下圖中從a到所有其它結點的最短路徑及長度。42例用Dijkstra算法求下圖中從a到所有其它結點的最短路步驟uS

abcdez0-01a{a}0422c{a,c}03210123b{a,c,b}0328124d{a,c,b,d}032810145e{a,c,b,d,e}032810136z{a,c,b,d,e,z}03281013l(v):=min{l(v),l(u)+wuv}43步驟uS例

用Dijkstra算法求下圖中從A到其它所有結點的最短路徑及長度44例用Dijkstra算法求下圖中從A到其它所有結點的最短路步驟uS

ABCDEFG0-01A{A}0712C{A,C}041543F{A,C,F}0411454114B{A,C,F,B}0411254115E{A,C,F,B,E}041125476G{A,C,F,B,E,G}04112547可以在Dijkstra算法的基礎之上以如下方法找到最短路徑：從終點往回走，找到它的前導頂點，使得它們之間的標號的差等于連接它們邊的權重，如此下去直至到起點，從而找到一條最短路徑。45步驟uS作業(yè)用Dijkstra算法求出下圖中從頂點a到其它所有頂點的最短路徑及及長度。46作業(yè)用Dijkstra算法求出下圖中從頂點a到其它所有頂點有向圖中求最短路徑的Dijkstra算法設Sj是帶權有向圖G中自頂點1到頂點j的最短有向路的長度步驟1：置P={1}，T={2,3,…,n}且S1=0，Sj=w1j，j=2,3,…,n。步驟2：在T中尋找一點k，使得Sk=min{Sj}，置P=P{k}，T=T-{k}。若T=，終止；否則，轉向步驟3。步驟3：對T中每一點j，置Sj=min{Sj，Sk+wkj}，然后轉向步驟2。算法經(jīng)過n-1次循環(huán)結束。47有向圖中求最短路徑的Dijkstra算法設Sj是帶權有向圖G任意兩點間的最短路徑Floyd算法Warshall算法48任意兩點間的最短路徑Floyd算法15任意兩點間的最短路徑-Floyd算法首先定義兩種矩陣運算：定義1

已知矩陣A=(aij)ml，B=(bij)l

n，規(guī)定C=AB=(cij)mn，其中cij=min(ai1+b1j,ai2+b2j,…,ail+blj)定義2

已知矩陣A=(aij)mn，B=(bij)mn，規(guī)定C=AB=(dij)mn，其中dij=min(aij,bij)49任意兩點間的最短路徑-Floyd算法首先定義兩種矩陣運算：1例已知矩陣W，求WW50例已知矩陣W，求WW17例已知矩陣W，求WWcij=min(ai1+b1j,ai2+b2j,…,ail+blj)51例已知矩陣W，求WWcij=min(ai1+b1j,acij=min(ai1+b1j,ai2+b2j,…,ail+blj)52cij=min(ai1+b1j,ai2+b2j,…,ai任意兩點間的最短路徑-Floyd算法算法原理：若W=(wij)nn是圖G的權矩陣，計算W[2]，W[3]，…，W[n]及S，其中W[k]=W[k-1]W=(wij[k])nn；

S=WW[2]W[3]

…W[n]=(sij)nn

。則wij[k]表示頂點i到頂點j經(jīng)過k條邊且權和最小的路徑，sij表示頂點i到頂點j權和最小的路徑（最短路徑）。53任意兩點間的最短路徑-Floyd算法算法原理：20例求下圖中任意兩點間最短路徑的長度。54例求下圖中任意兩點間最短路徑的長度。215522由s16知，頂點v1到v6的最短路徑為6；由s35知，頂點v3到v5的最短路徑為2；由s45知，頂點v4到v5沒有最短路徑；56由s16知，頂點v1到v6的最短路徑為6；23任意兩點間的最短路徑-Warshall算法算法原理：（1）輸入圖G的權矩陣W；（2）置k:=1；（3）置i:=1；（4）修改矩陣W中的權值，

wij:=min(wij,wik+wkj)，j=1,2,…,n；（5）i:=i+1，若in，轉(4)；（6）k:=k+1，若kn，轉(3)；否則停止。57任意兩點間的最短路徑-Warshall算法算法原理：24例求下圖中任意兩點間最短路徑的長度。wij

:=min(wij,wik+wkj)58例求下圖中任意兩點間最短路徑的長度。wij:=min(wwij:=min(wij