最短路徑算法課件

8.3單源最短路徑

給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。 1、算法基本思想 Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。8.3單源最短路徑 給定帶權(quán)有向圖G=(V,E)，其中8.3單源最短路徑

其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。8.3單源最短路徑 其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地8.3單源最短路徑

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。8.3單源最短路徑 例如，對(duì)右圖中的有向圖，應(yīng)用Dijk8.3單源最短路徑迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代過(guò)程：

8.3單源最短路徑迭代Sudist[2]dist[3]di

初始狀態(tài)下，S中只有一個(gè)點(diǎn)（源點(diǎn)v1）。-11-111010∞3010010000s:distance:path:① 初始狀態(tài)下，S中只有一個(gè)點(diǎn)（源點(diǎn)v1）。-11-1110

第二步，將S外距離S最近的點(diǎn)v2加入S。更新相應(yīng)信息。-11-111010∞3010010000s:distance:path:1①②602 第二步，將S外距離S最近的點(diǎn)v2加入S。更新相應(yīng)信息。-

第三步，將S外距離S最近的點(diǎn)v4加入S。更新相應(yīng)信息。-11211010603010011000s:distance:path:1①②504④904 第三步，將S外距離S最近的點(diǎn)v4加入S。更新相應(yīng)信息。-

第四步，將S外距離S最近的點(diǎn)v3加入S。更新相應(yīng)信息。-1141401050309011010s:distance:path:1①②603④③ 第四步，將S外距離S最近的點(diǎn)v3加入S。更新相應(yīng)信息。-

第五步，將S外距離S最近的點(diǎn)v5加入S。更新相應(yīng)信息。-1141301050306011110s:distance:path:1①②④③⑤ 第五步，將S外距離S最近的點(diǎn)v5加入S。更新相應(yīng)信息。-voidDijkstra(intG[][N],intv0,intdistance[],intpath[]，intn)//源點(diǎn)v0到其他頂點(diǎn)的最短距離distance和最短路徑下標(biāo)path{int*s=newint［n］;intminDis,i,j,u;

//初始化三個(gè)數(shù)組

voidDijkstra(intG[][N],int//逐次將各點(diǎn)加入S//在當(dāng)前還未找到最短路徑的頂點(diǎn)集中選取具有最短距離的頂點(diǎn)u//標(biāo)記頂點(diǎn)u已從集合T加入到集合S中//修改從v0到其他頂點(diǎn)的最短距離和最短路徑//逐次將各點(diǎn)加入SvoidDijkstra(intG[][N],intv0,intdistance[],intpath[]，intn)//從源點(diǎn)v0到其他頂點(diǎn)的最短距離distance和最短路徑下標(biāo)path{int*s=newint［n］;intminDis,i,j,u;

//初始化三個(gè)數(shù)組for(i=0;i<n;i++){voidDijkstra(intG[][N],intdistance［i］=G[v0][i];s［i］=0;if(I!=v0&&distance［i］<MAX)path［i］=v0;elsepath［i］=-1;}s［v0］=1;//標(biāo)記頂點(diǎn)v0已從集合T加入到集合S中//在當(dāng)前還未找到最短路徑的頂點(diǎn)集中選取具有最短距離的頂點(diǎn)ufor(i=1;i<n;i++){minDis=MAX;for(j=0;j<=n;j++)distance［i］=G[v0][i];u到j(luò)有邊相連，j才有可能因u的加入而距離源點(diǎn)更近if(s［j］==0&&distance［j］<minDis){u=j;minDis=distance［j］;}s［u］=1;//標(biāo)記頂點(diǎn)u已從集合T加入到集合S中//修改從v0到其他頂點(diǎn)的最短距離和最短路徑for(j=0;j<n;j++)if(s[j]==0&&G[u][j]<MAX&&distance[u]+G[u][j]<distance[j])u到j(luò)有邊相連，j才有可能因u的加入而距離源點(diǎn)更近if(s［distance[j]=distance[u]+G[u][j];path[j]=u;}}}distance[j]=distance[u]+G[u][j2、算法的正確性和計(jì)算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計(jì)算復(fù)雜性 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過(guò)。2、算法的正確性和計(jì)算復(fù)雜性7.5所有點(diǎn)對(duì)的最短路徑問(wèn)題對(duì)于一個(gè)各邊權(quán)值均大于0的有n個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，求所有頂點(diǎn)之間的最短路徑和最短距離。圖的鄰接矩陣表示法123V=(b)(a)28196123L=

029061∞07.5所有點(diǎn)對(duì)的最短路徑問(wèn)題對(duì)于一個(gè)各邊權(quán)值均大于0的有n個(gè)復(fù)習(xí)Dijkstra算法其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源點(diǎn)。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源點(diǎn)到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組distance記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組distance作必要的修改。一旦S包含了所有V中頂點(diǎn)，distance就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。復(fù)習(xí)Dijkstra算法其基本思想是，設(shè)置頂點(diǎn)集合算法中，我們不斷更新以下三個(gè)數(shù)組：s數(shù)組:s[i]，當(dāng)頂點(diǎn)i加入S時(shí)，s[i]置1Distance數(shù)組:Distance[i]記錄原點(diǎn)到頂點(diǎn)i的最短特殊路徑長(zhǎng)度。path數(shù)組：path[i]記錄頂點(diǎn)i在其最短特殊路徑上的前驅(qū)頂點(diǎn)。由該數(shù)組可求得原點(diǎn)到各點(diǎn)的最短路徑。如：設(shè)源點(diǎn)是頂點(diǎn)1,path數(shù)組如下算法中，我們不斷更新以下三個(gè)數(shù)組：

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。0141301050306011111s:distance:path:由源點(diǎn)1到頂點(diǎn)5的路徑為：1->4->3->5 例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源方法一：重復(fù)調(diào)用Dijkstra算法n次可輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)調(diào)用狄克斯特拉算法函數(shù)Dijkstra()n次，即可求得所有頂點(diǎn)之間的最短路徑和最短距離。利用Dijkstra()函數(shù)求所有頂點(diǎn)之間的最短路徑算法如下。其中，distance[i][j]中存放著從頂點(diǎn)i到頂點(diǎn)j的最短距離，path[i][j]中存放著從頂點(diǎn)i到頂點(diǎn)j的最短路徑的前一頂點(diǎn)下標(biāo)。方法一：重復(fù)調(diào)用Dijkstra算法n次可輪流以每一個(gè)頂點(diǎn)為voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance［i］,path［i］);}由于狄克斯特拉算法的時(shí)間復(fù)雜度是O(n2)，所以n次調(diào)用狄克斯特拉算法的時(shí)間復(fù)雜度是O(n3)。voidShortPath(AdjMWGraph&G,i該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)例如上圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)例如上圖中，若路線子問(wèn)題的構(gòu)造原問(wèn)題：每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短距離最小的子問(wèn)題D0：從頂點(diǎn)i（不得經(jīng)過(guò)任何其他頂點(diǎn)）到頂點(diǎn)j的距離；子問(wèn)題D1：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1，不得經(jīng)過(guò)其他任何其他頂點(diǎn)）到頂點(diǎn)j的距離。子問(wèn)題的構(gòu)造原問(wèn)題：每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短距離子問(wèn)題Dk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k，不得經(jīng)過(guò)任何其他頂點(diǎn)）到頂點(diǎn)j的距離。子問(wèn)題Dn：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)n）到頂點(diǎn)j的距離?！丛瓎?wèn)題子問(wèn)題Dk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k，不遞推關(guān)系的建立由di,jk-1推出di,jk的過(guò)程如下若k=0,di,jk=L[i][j](因?yàn)閺膇到j(luò)不允許經(jīng)過(guò)任何其他頂點(diǎn)）若1≤k≤n,di,jk=min{di,jk-1,di,kk-1+dk,jk-1}子問(wèn)題Dk-1：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……、頂點(diǎn)k-1）到頂點(diǎn)j的距離。

子問(wèn)題Dk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k-1、頂點(diǎn)k）到頂點(diǎn)j的距離。從子問(wèn)題Dk-1：到子問(wèn)題Dk，僅僅多考慮了一個(gè)頂點(diǎn)k。我們需要重新考慮從i到j(luò)的距離：

頂點(diǎn)i到頂點(diǎn)j，是不是從k走會(huì)更近？如果從頂點(diǎn)i到頂點(diǎn)j從頂點(diǎn)k走更近，則i到j(luò)的距離di,jk=i到k的距離di,kk-1

+

k到j(luò)的距離dk,jk-1如果頂點(diǎn)i到頂點(diǎn)j從頂點(diǎn)k走更遠(yuǎn)，甚至走不通，則保持原來(lái)的距離不變di,jk=di,jk-1

。由di,jk-1推出di,jk的過(guò)程，主要考慮的是頂點(diǎn)k的加入會(huì)引起什么變化？由不允許路過(guò)頂點(diǎn)k到允許路過(guò)頂點(diǎn)k，有些點(diǎn)間的距離是否會(huì)變的更近。遞推關(guān)系的建立由di,jk-1推出di,jk的過(guò)程如下子例：考慮下圖所示的帶權(quán)有向圖，求所有頂點(diǎn)之間的最短距離。V=(b)(a)12328196123L=

029061∞0計(jì)算過(guò)程例：考慮下圖所示的帶權(quán)有向圖，求所有頂點(diǎn)之間的最短距離。V12328196029061∞0D0=029806130D1=028806130D2=028706130D3=Di,jk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k）到頂點(diǎn)j的距離。在D1中，第1行和第一列是不變的，因?yàn)檎f(shuō)從頂點(diǎn)1到頂點(diǎn)j或頂點(diǎn)j到頂點(diǎn)1：允許經(jīng)過(guò)頂點(diǎn)1是沒(méi)有意義的D1[2][3]:從頂點(diǎn)2到頂點(diǎn)3的距離（可以經(jīng)過(guò)頂點(diǎn)1）（1）不經(jīng)過(guò)頂點(diǎn)1：仍是D0[2][3]=6；（2）過(guò)頂點(diǎn)1：D0[2][1]+D0[1][3]=8+9=17取最小值6D1[3][2]:從頂點(diǎn)3到頂點(diǎn)2的距離（可以經(jīng)過(guò)頂點(diǎn)1）（1）不經(jīng)過(guò)頂點(diǎn)1：仍是D0[3][2]=∞

；（2）過(guò)頂點(diǎn)1：D0[3][1]+D0[1][2]=1+2=3取最小值3D2[1][3]:從頂點(diǎn)1到頂點(diǎn)3的距離（也可以經(jīng)過(guò)頂點(diǎn)2）（1）不經(jīng)過(guò)頂點(diǎn)2：仍是D1[1][3]=9；（2）過(guò)頂點(diǎn)2：D1[1][2]+D1[2][3]=2+6=8取最小值812328196029D0=02算法設(shè)計(jì)重要發(fā)現(xiàn)：在從Dk-1到Dk的計(jì)算過(guò)程中中，第k行和第k列是不變的。（因?yàn)檎f(shuō)從頂點(diǎn)k到頂點(diǎn)j或頂點(diǎn)j到頂點(diǎn)k允許經(jīng)過(guò)頂點(diǎn)k是沒(méi)有意義的）

而在從Dk-1到Dk的計(jì)算過(guò)程中也只用到第k行和第k列，也就是說(shuō)，在這一步的計(jì)算過(guò)程中用到的數(shù)據(jù)都不會(huì)被覆蓋。故在算法中僅使用一個(gè)矩陣D即可算法設(shè)計(jì)重要發(fā)現(xiàn)：在從Dk-1到Dk的計(jì)算過(guò)程中中，第k行和FLOYD算法FLOYD(int*L,intn){int*D=(int*)malloc((n+1)*(n+1)*sizeof(int));DL{將數(shù)組L復(fù)制到D};for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)D[i*n+j]=min(D[i*n+j],D[i*n+k]+D[k*n+j]);}FLOYD算法FLOYD(int*L,intn)8.3單源最短路徑

給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。 1、算法基本思想 Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。8.3單源最短路徑 給定帶權(quán)有向圖G=(V,E)，其中8.3單源最短路徑

其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。8.3單源最短路徑 其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地8.3單源最短路徑

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。8.3單源最短路徑 例如，對(duì)右圖中的有向圖，應(yīng)用Dijk8.3單源最短路徑迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代過(guò)程：

8.3單源最短路徑迭代Sudist[2]dist[3]di

初始狀態(tài)下，S中只有一個(gè)點(diǎn)（源點(diǎn)v1）。-11-111010∞3010010000s:distance:path:① 初始狀態(tài)下，S中只有一個(gè)點(diǎn)（源點(diǎn)v1）。-11-1110

第二步，將S外距離S最近的點(diǎn)v2加入S。更新相應(yīng)信息。-11-111010∞3010010000s:distance:path:1①②602 第二步，將S外距離S最近的點(diǎn)v2加入S。更新相應(yīng)信息。-

第三步，將S外距離S最近的點(diǎn)v4加入S。更新相應(yīng)信息。-11211010603010011000s:distance:path:1①②504④904 第三步，將S外距離S最近的點(diǎn)v4加入S。更新相應(yīng)信息。-

第四步，將S外距離S最近的點(diǎn)v3加入S。更新相應(yīng)信息。-1141401050309011010s:distance:path:1①②603④③ 第四步，將S外距離S最近的點(diǎn)v3加入S。更新相應(yīng)信息。-

第五步，將S外距離S最近的點(diǎn)v5加入S。更新相應(yīng)信息。-1141301050306011110s:distance:path:1①②④③⑤ 第五步，將S外距離S最近的點(diǎn)v5加入S。更新相應(yīng)信息。-voidDijkstra(intG[][N],intv0,intdistance[],intpath[]，intn)//源點(diǎn)v0到其他頂點(diǎn)的最短距離distance和最短路徑下標(biāo)path{int*s=newint［n］;intminDis,i,j,u;

//初始化三個(gè)數(shù)組

voidDijkstra(intG[][N],int//逐次將各點(diǎn)加入S//在當(dāng)前還未找到最短路徑的頂點(diǎn)集中選取具有最短距離的頂點(diǎn)u//標(biāo)記頂點(diǎn)u已從集合T加入到集合S中//修改從v0到其他頂點(diǎn)的最短距離和最短路徑//逐次將各點(diǎn)加入SvoidDijkstra(intG[][N],intv0,intdistance[],intpath[]，intn)//從源點(diǎn)v0到其他頂點(diǎn)的最短距離distance和最短路徑下標(biāo)path{int*s=newint［n］;intminDis,i,j,u;

//初始化三個(gè)數(shù)組for(i=0;i<n;i++){voidDijkstra(intG[][N],intdistance［i］=G[v0][i];s［i］=0;if(I!=v0&&distance［i］<MAX)path［i］=v0;elsepath［i］=-1;}s［v0］=1;//標(biāo)記頂點(diǎn)v0已從集合T加入到集合S中//在當(dāng)前還未找到最短路徑的頂點(diǎn)集中選取具有最短距離的頂點(diǎn)ufor(i=1;i<n;i++){minDis=MAX;for(j=0;j<=n;j++)distance［i］=G[v0][i];u到j(luò)有邊相連，j才有可能因u的加入而距離源點(diǎn)更近if(s［j］==0&&distance［j］<minDis){u=j;minDis=distance［j］;}s［u］=1;//標(biāo)記頂點(diǎn)u已從集合T加入到集合S中//修改從v0到其他頂點(diǎn)的最短距離和最短路徑for(j=0;j<n;j++)if(s[j]==0&&G[u][j]<MAX&&distance[u]+G[u][j]<distance[j])u到j(luò)有邊相連，j才有可能因u的加入而距離源點(diǎn)更近if(s［distance[j]=distance[u]+G[u][j];path[j]=u;}}}distance[j]=distance[u]+G[u][j2、算法的正確性和計(jì)算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計(jì)算復(fù)雜性 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過(guò)。2、算法的正確性和計(jì)算復(fù)雜性7.5所有點(diǎn)對(duì)的最短路徑問(wèn)題對(duì)于一個(gè)各邊權(quán)值均大于0的有n個(gè)頂點(diǎn)的帶權(quán)有向圖G=(V,E)，求所有頂點(diǎn)之間的最短路徑和最短距離。圖的鄰接矩陣表示法123V=(b)(a)28196123L=

029061∞07.5所有點(diǎn)對(duì)的最短路徑問(wèn)題對(duì)于一個(gè)各邊權(quán)值均大于0的有n個(gè)復(fù)習(xí)Dijkstra算法其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源點(diǎn)。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源點(diǎn)到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組distance記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組distance作必要的修改。一旦S包含了所有V中頂點(diǎn)，distance就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。復(fù)習(xí)Dijkstra算法其基本思想是，設(shè)置頂點(diǎn)集合算法中，我們不斷更新以下三個(gè)數(shù)組：s數(shù)組:s[i]，當(dāng)頂點(diǎn)i加入S時(shí)，s[i]置1Distance數(shù)組:Distance[i]記錄原點(diǎn)到頂點(diǎn)i的最短特殊路徑長(zhǎng)度。path數(shù)組：path[i]記錄頂點(diǎn)i在其最短特殊路徑上的前驅(qū)頂點(diǎn)。由該數(shù)組可求得原點(diǎn)到各點(diǎn)的最短路徑。如：設(shè)源點(diǎn)是頂點(diǎn)1,path數(shù)組如下算法中，我們不斷更新以下三個(gè)數(shù)組：

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。0141301050306011111s:distance:path:由源點(diǎn)1到頂點(diǎn)5的路徑為：1->4->3->5 例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源方法一：重復(fù)調(diào)用Dijkstra算法n次可輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)調(diào)用狄克斯特拉算法函數(shù)Dijkstra()n次，即可求得所有頂點(diǎn)之間的最短路徑和最短距離。利用Dijkstra()函數(shù)求所有頂點(diǎn)之間的最短路徑算法如下。其中，distance[i][j]中存放著從頂點(diǎn)i到頂點(diǎn)j的最短距離，path[i][j]中存放著從頂點(diǎn)i到頂點(diǎn)j的最短路徑的前一頂點(diǎn)下標(biāo)。方法一：重復(fù)調(diào)用Dijkstra算法n次可輪流以每一個(gè)頂點(diǎn)為voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance［i］,path［i］);}由于狄克斯特拉算法的時(shí)間復(fù)雜度是O(n2)，所以n次調(diào)用狄克斯特拉算法的時(shí)間復(fù)雜度是O(n3)。voidShortPath(AdjMWGraph&G,i該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)例如上圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)例如上圖中，若路線子問(wèn)題的構(gòu)造原問(wèn)題：每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短距離最小的子問(wèn)題D0：從頂點(diǎn)i（不得經(jīng)過(guò)任何其他頂點(diǎn)）到頂點(diǎn)j的距離；子問(wèn)題D1：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1，不得經(jīng)過(guò)其他任何其他頂點(diǎn)）到頂點(diǎn)j的距離。子問(wèn)題的構(gòu)造原問(wèn)題：每個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短距離子問(wèn)題Dk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k，不得經(jīng)過(guò)任何其他頂點(diǎn)）到頂點(diǎn)j的距離。子問(wèn)題Dn：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)n）到頂點(diǎn)j的距離?！丛瓎?wèn)題子問(wèn)題Dk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k，不遞推關(guān)系的建立由di,jk-1推出di,jk的過(guò)程如下若k=0,di,jk=L[i][j](因?yàn)閺膇到j(luò)不允許經(jīng)過(guò)任何其他頂點(diǎn)）若1≤k≤n,di,jk=min{di,jk-1,di,kk-1+dk,jk-1}子問(wèn)題Dk-1：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……、頂點(diǎn)k-1）到頂點(diǎn)j的距離。

子問(wèn)題Dk：從頂點(diǎn)i（可以經(jīng)過(guò)頂點(diǎn)1、頂點(diǎn)2、……頂點(diǎn)k-1、頂點(diǎn)k）到頂點(diǎn)j的距離。從子問(wèn)題Dk-1：到子問(wèn)題Dk，僅僅多考慮了一個(gè)頂點(diǎn)k。我們需要重新考慮從i到j(luò)的距離：

頂點(diǎn)i到頂點(diǎn)j，是不是從k走會(huì)更近？如果從頂點(diǎn)i到頂點(diǎn)j從頂點(diǎn)k走更近，則i到j(luò)的距離di,jk=i到k的距離di,kk-1

+

k到j(luò)的距離dk,jk-1如果頂點(diǎn)i到頂點(diǎn)j從頂點(diǎn)k走更遠(yuǎn)，甚至走不通，則保持原來(lái)的距離不變di,jk=di,jk-1

。由di,jk-1推出di,jk的過(guò)程，主要考慮的是頂點(diǎn)k的加入會(huì)引起什么變化？由不允許路過(guò)頂點(diǎn)k到