數(shù)據(jù)結(jié)構(gòu)主講人：楊丹常州信息職業(yè)技術(shù)學(xué)院5.6最短路徑在一個圖中，若從一個頂點到另外一個頂點存在路徑，路徑長度就是一條路徑上所經(jīng)過的邊的數(shù)目。圖中從一個頂點到另外一個頂點可能存在多條路徑，路徑長度最短的那條路徑叫做最短路徑，其路徑長度稱為最短路徑長度或最短距離。引言IntroductionPart01帶權(quán)圖的最短路徑在一個帶權(quán)圖中，若從一個頂點到另外一個頂點存在一條路徑，則稱該路徑上所經(jīng)過邊的權(quán)值之和為該路徑上的帶權(quán)路徑長度。帶權(quán)圖中從一個頂點到另外一個頂點可能存在著許多條路徑，帶權(quán)路徑長度值最小的那條路徑稱為最短路徑，其帶權(quán)路徑長度叫做最短路徑長度或最短距離。帶權(quán)圖可以分為有向圖和無向圖。如果把無向帶權(quán)圖的每一條邊(u,v)都定義為弧<u,v>和弧<v,u>，則無向帶權(quán)圖也就可以轉(zhuǎn)換為有向帶權(quán)圖。不失一般性，這里討論有向帶權(quán)圖的最短路徑問題。最短路徑說明帶權(quán)圖的最短路徑帶權(quán)圖的最短路徑5示例示例左圖所示的有向帶權(quán)圖從頂點A到頂點D有四條路徑，分別是路徑(A,D)，其帶權(quán)路徑長度為30；路徑(A,C,F,D)，其帶權(quán)路徑長度為22；路徑(A,C,F,E,D)，其帶權(quán)路徑長度為34；路徑(A,C,B,E,D)，其帶權(quán)路徑長度為32。路徑(A,C,F,D)稱為最短路徑，其帶權(quán)路徑長度22為最短距離。Part02單源最短路徑設(shè)有一個有向帶權(quán)圖G=(V,E)，其中每條邊的權(quán)是一個非負實數(shù)，給定V中的一個頂點，稱為源點（Source），求從源點到所有其他各頂點的最短路徑長度（長度是指路徑上各邊權(quán)之和）的問題稱為單源最短路徑問題（SingleSourceShortestPaths）。

對于有向帶權(quán)圖從一個確定頂點（稱為源點）到其余各頂點的最短路徑問題，迪杰斯特拉（Dijkstra）提出了一個按路徑長度遞增的順序逐步產(chǎn)生最短路徑的構(gòu)造方法。單源最短路徑單源最短路徑基本思想迪杰斯特拉（Dijkstra）算法將頂點集V分成S（開始只包含源點s，S包含的點都是已經(jīng)計算出最短路徑的點）和V-S集合（V-S包含那些未確定最短路徑的點）；如此反復(fù)，直到V-S變空集為止。從V-S中選取這樣一個頂點w：滿足經(jīng)過S集合中任意頂點v到w的路徑最短，即滿足{v到w的路徑}最小的那個w。其中v屬于S，w屬于V-S。將w加入S，并從V-S中移除w；Dijkstra算法步驟【例】用迪杰斯特拉（Dijkstra）算法求下圖G中頂點A到其余各頂點的最短距離。圖GDijkstra算法步驟Dijkstra算法步驟Dijkstra算法步驟源點中間頂點終點路徑長度ACB20A

C5AC,FD22AC,BE28ACF12表

源點到其他各頂點的最短路徑【例】用迪杰斯特拉（Dijkstra）算法求下圖G中頂點A到其余各頂點的最短距離。Dijkstra算法實現(xiàn)distance[]用于存放源點到其余頂點的最短距離數(shù)值path[]表示從源點v到其余頂點的最短路徑上到達目標(biāo)頂點的前一個頂點boolean類型數(shù)組selected，selected[i](i=0,1,…n-1)用來標(biāo)記是否已經(jīng)確定源點v到第i