dijisktra算法梳理和代碼

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

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

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

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

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

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

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

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

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