dijisktra算法梳理和代碼

1、Dijkstra 算法孫玉潔歸納迪杰斯特拉(Dijkstra)算法是典型最短路徑算法，用于計算一個節(jié)點到其他節(jié)點的 最短路徑。它的主要特點是以起始點為中心向外層層擴展(廣度優(yōu)先搜索思想)，直到擴展到 終點為止?；舅枷胪ㄟ^Dijkstra計算圖G中的最短路徑時，需要指定起點s(即從頂點s開始計算)。此外，引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點(以及相應 的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(以及該頂點到起點s 的距離)。初始時，S中只有起點s； U中是除s之外的頂點，并且U中頂點的路徑是”起 點s到該頂點的路徑”。然后，從U中找出路徑最短的頂點，并將其加入到S

2、中；接著，更新U中的頂點和頂點對應的路徑。然后，再從U中找出路徑最短 的頂點，并將其加入到S中；接著，更新U中的頂點和頂點對應的路徑。重 復該操作，直到遍歷完所有頂點。操作步驟初始時，S只包含起點s； U包含除s外的其他頂點，且U中頂點的距離為”起 點s到該頂點的距離”例如，U中頂點v的距離為(s,v)的長度，然后s和v不 相鄰，則v的距離為o從U中選出”距離最短的頂點k”，并將頂點k加入到S中；同時，從U中移 除頂點k。更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離，是由于上一 步中確定了 k是求出最短路徑的頂點，從而可以利用k來更新其它頂點的距離； 例如，(s,v)的距離可能大于

3、(s,k)+(k,v)的距離。重復步驟(2)和(3),直到遍歷完所有頂點。單純的看上面的理論可能比較難以理解，下面通過實例來對該算法進行說明。10BKi5D211G4以上圖10BKi5D211G4以上圖G4為例，來對迪杰斯特拉進行算法演示（以第4個頂點D為起點）。以下B節(jié)點中23應為13。WB16A5214B節(jié)點中23應為13。WB16A5214GE第1埶 選取頂點D險 M)I4 I;| I血）5是己計斛最崩卷的定點的集合| | 繼）曜未計黜罐騒酬定融集合I I |（03）C表示覆點（倒起點曲最毎距富是3 初始狀態(tài)：S是已計算出最短路徑的頂點集合，U是未計算除最短路徑的頂點的 集合！ 第1步：

4、將頂點D加入到S中。此時，S=D(O), U=A(),BM，C(3),E(4),F(g),GM。注:C(3)表示 C 到起點 D的距離是3。第2步：將頂點C加入到S中。上一步操作之后，U中頂點C到起點D的距離最短；因此，將C加入到S中， 同時更新U中頂點的距離。以頂點F為例，之前F到D的距離為X；但是將C 加入到S之后，F(xiàn)到D的距離為9=(F,C)+(C,D)。此時，S=D(0),C(3), U=A(-),B(23),E(4),F(9),G(*)。第3步：將頂點E加入到S中。上一步操作之后，U中頂點E到起點D的距離最短；因此，將E加入到S中， 同時更新U中頂點的距離。還是以頂點F為例，之前F到

5、D的距離為9；但是 將E加入到S之后，F(xiàn)到D的距離為6=(F,E)+(E,D)。此時，S=D(0),C(3),E(4), U=A(-),B(23),F(6),G(12)。第4步：將頂點F加入到S中。此時，S=D(0),C(3),E(4),F(6), U=A(22),B(13),G(12)。第5步：將頂點G加入到S中。此時，S=D(0),C(3),E(4),F(6),G(12), U=A(22),B(13)。第6步：將頂點B加入到S中。此時，S=D(0),C(3),E(4),F(6),G(12),B(13), U=A(22)。第7步：將頂點A加入到S中。此時，S=D(0),C(3),E(4),F

6、(6),G(12),B(13),A(22)。此時，起點D到各個頂點的最短距離就計算出來了： A(22) B(13) C(3) D(0) E(4)F(6) G(12)。代碼(孫玉潔收錄)鄰接矩陣為例/鄰接矩陣 typedef struct _graphchar vexsMAX;/頂點集合int vex num;/頂點數(shù)int edg num;/邊數(shù)int matrixMAXMAX; / 鄰接矩陣Graph, *PGraph;/邊的結(jié)構(gòu)體typedef struct _EdgeDatachar start; / 邊的起點chare nd; /邊的終點int weight; /邊的權(quán)重EData;解

7、釋：Graph是鄰接矩陣對應的結(jié)構(gòu)體。vexs用于保存頂點，vex num是頂點數(shù)，edg num是邊數(shù)；matrix則是用于保存 矩陣信息的二維數(shù)組。例如，matrixij=1，則表示”頂點i（即vexsi） ”和”頂點j（即vexsj） ”是鄰接 點；matrixij=O，則表示它們不是鄰接點。EData是鄰接矩陣邊對應的結(jié)構(gòu)體。Dijkstra算法代碼/* Dijkstra 最短路徑。*即，統(tǒng)計圖(G)中頂點vs到其它各個頂點的最短路徑。* 參數(shù)說明：G - 圖vs -起始頂點(start vertex)。即計算頂點vs到其它頂點的最短路徑。prev -前驅(qū)頂點數(shù)組。即，previ的值是

8、頂點vs到頂點i的最短路徑所經(jīng)歷的全 部頂點中，位于頂點i之前的那個頂點。dist -長度數(shù)組。即，disti是頂點vs到頂點i的最短路徑的長度。*/void dijkstra(Graph G, int vs, int prev, int dist)int i,j,k;int min;int tmp;int flagMAX; / flagi=1表示頂點vs到頂點i的最短路徑已成功獲取。/ 初始化for (i = 0; i G.vexnum; i+)flagi = 0;previ = 0;/ 頂點 i 的最短路徑還沒獲取到。/ 頂點 i 的前驅(qū)頂點為 0。disti = G.matrixvsi;

9、頂點i的最短路徑為頂點vs到頂點i的權(quán)。 /對頂點vs自身進行初始化flagvs = 1;distvs = 0;/ 遍歷 G.vexnum-1 次；每次找出一個頂點的最短路徑。for (i = 1; i G.vexnum; i+) / 尋找當前最小的路徑；/即，在未獲取最短路徑的頂點中，找到離vs最近的頂點(k)。min = INF;for (j = 0; j G.vexnum; j+)if (flagj=0 & distjmin)min = distj; k = j;/標記頂點k為已經(jīng)獲取到最短路徑flagk = 1;/ 修正當前最短路徑和前驅(qū)頂點/即，當已經(jīng)頂點k的最短路徑之后，更新未獲取最短路徑的頂點的最短路徑 和前驅(qū)頂點。for (j = 0; j G.vexnum; j+)tmp = (G.matrixkj=INF ? INF : (min + G.matrixkj); / 防止溢出if (flagj = 0 & (tmp distj) ) distj = t