本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。

dijkstra算法(一)之 C語言詳解

本章介紹迪杰斯特拉算法。和以往一樣，本文會先對迪杰斯特拉算法的理論論知識進(jìn)行介紹，，然后給出C語言的實(shí)現(xiàn)。后續(xù)再分別給出C++和Java版本的實(shí)現(xiàn)。

目錄
1.
2.
3.
4.

轉(zhuǎn)載請注明出處：

更多內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法系列 目錄

迪杰斯特拉(Dijkstra)算法是典型最短路徑算法，用于計算一個節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。
它的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止。

基本思想

     通過Dijkstra計算圖G中的最短路徑時，需要指定起點(diǎn)s(即從頂點(diǎn)s開始計算)。

     此外，引進(jìn)兩個集合S和U。S的作用是記錄已求出最短路徑的頂點(diǎn)(以及相應(yīng)的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(diǎn)(以及該頂點(diǎn)到起點(diǎn)s的距離)。

     初始時，S中只有起點(diǎn)s；U中是除s之外的頂點(diǎn)，并且U中頂點(diǎn)的路徑是"起點(diǎn)s到該頂點(diǎn)的路徑"。然后，從U中找出路徑最短的頂點(diǎn)，并將其加入到S中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對應(yīng)的路徑。 然后，再從U中找出路徑最短的頂點(diǎn)，并將其加入到S中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對應(yīng)的路徑。 ... 重復(fù)該操作，直到遍歷完所有頂點(diǎn)。

操作步驟

(1) 初始時，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的距離為∞]。

(2) 從U中選出"距離最短的頂點(diǎn)k"，并將頂點(diǎn)k加入到S中；同時，從U中移除頂點(diǎn)k。

(3) 更新U中各個頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來更新其它頂點(diǎn)的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。

(4) 重復(fù)步驟(2)和(3)，直到遍歷完所有頂點(diǎn)。

單純的看上面的理論可能比較難以理解，下面通過實(shí)例來對該算法進(jìn)行說明。

以上圖G4為例，來對迪杰斯特拉進(jìn)行算法演示(以第4個頂點(diǎn)D為起點(diǎn))。

初始狀態(tài)：S是已計算出最短路徑的頂點(diǎn)集合，U是未計算除最短路徑的頂點(diǎn)的集合！
第1步：將頂點(diǎn)D加入到S中。
    此時，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。     注:C(3)表示C到起點(diǎn)D的距離是3。

第2步：將頂點(diǎn)C加入到S中。
    上一步操作之后，U中頂點(diǎn)C到起點(diǎn)D的距離最短；因此，將C加入到S中，同時更新U中頂點(diǎn)的距離。以頂點(diǎn)F為例，之前F到D的距離為∞；但是將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步：將頂點(diǎn)E加入到S中。
    上一步操作之后，U中頂點(diǎn)E到起點(diǎn)D的距離最短；因此，將E加入到S中，同時更新U中頂點(diǎn)的距離。還是以頂點(diǎn)F為例，之前F到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步：將頂點(diǎn)F加入到S中。
    此時，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。

第5步：將頂點(diǎn)G加入到S中。
    此時，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。

第6步：將頂點(diǎn)B加入到S中。
    此時，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。

第7步：將頂點(diǎn)A加入到S中。
    此時，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

此時，起點(diǎn)D到各個頂點(diǎn)的最短距離就計算出來了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。

以"鄰接矩陣"為例對迪杰斯特拉算法進(jìn)行說明，對于"鄰接表"實(shí)現(xiàn)的圖在后面會給出相應(yīng)的源碼。

1. 基本定義

// 鄰接矩陣 typedef struct _graph { char vexs[MAX]; // 頂點(diǎn)集合 int vexnum; // 頂點(diǎn)數(shù) int edgnum; // 邊數(shù) int matrix[MAX][MAX]; // 鄰接矩陣 }Graph, *PGraph; // 邊的結(jié)構(gòu)體 typedef struct _EdgeData { char start; // 邊的起點(diǎn) char end; // 邊的終點(diǎn) int weight; // 邊的權(quán)重 }EData;

Graph是鄰接矩陣對應(yīng)的結(jié)構(gòu)體。
vexs用于保存頂點(diǎn)，vexnum是頂點(diǎn)數(shù)，edgnum是邊數(shù)；matrix則是用于保存矩陣信息的二維數(shù)組。例如，matrix[i][j]=1，則表示"頂點(diǎn)i(即vexs[i])"和"頂點(diǎn)j(即vexs[j])"是鄰接點(diǎn)；matrix[i][j]=0，則表示它們不是鄰接點(diǎn)。
EData是鄰接矩陣邊對應(yīng)的結(jié)構(gòu)體。

2. 迪杰斯特拉算法

/* * Dijkstra最短路徑。 * 即，統(tǒng)計圖(G)中"頂點(diǎn)vs"到其它各個頂點(diǎn)的最短路徑。 * * 參數(shù)說明： * G -- 圖 * vs -- 起始頂點(diǎn)(start vertex)。即計算"頂點(diǎn)vs"到其它頂點(diǎn)的最短路徑。 * prev -- 前驅(qū)頂點(diǎn)數(shù)組。即，prev[i]的值是"頂點(diǎn)vs"到"頂點(diǎn)i"的最短路徑所經(jīng)歷的全部頂點(diǎn)中，位于"頂點(diǎn)i"之前的那個頂點(diǎn)。 * dist -- 長度數(shù)組。即，dist[i]是"頂點(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 flag[MAX]; // flag[i]=1表示"頂點(diǎn)vs"到"頂點(diǎn)i"的最短路徑已成功獲取。 // 初始化 for (i = 0; i < G.vexnum; i++) { flag[i] = 0; // 頂點(diǎn)i的最短路徑還沒獲取到。 prev[i] = 0; // 頂點(diǎn)i的前驅(qū)頂點(diǎn)為0。 dist[i] = G.matrix[vs][i];// 頂點(diǎn)i的最短路徑為"頂點(diǎn)vs"到"頂點(diǎn)i"的權(quán)。 } // 對"頂點(diǎn)vs"自身進(jìn)行初始化 flag[vs] = 1; dist[vs] = 0; // 遍歷G.vexnum-1次；每次找出一個頂點(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 (flag[j]==0 && dist[j]<min) { min = dist[j]; k = j; } } // 標(biāo)記"頂點(diǎn)k"為已經(jīng)獲取到最短路徑 flag[k] = 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.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出 if (flag[j] == 0 && (tmp < dist[j]) ) { dist[j] = tmp; prev[j] = k; } } } // 打印dijkstra最短路徑的結(jié)果 printf("dijkstra(%c): \n", G.vexs[vs]); for (i = 0; i < G.vexnum; i++) printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]); }

這里分別給出"鄰接矩陣圖"和"鄰接表圖"的迪杰斯特拉算法源碼。

1. 鄰接矩陣源碼(matrix_udg.c)

2. 鄰接表源碼(list_udg.c)

posted on

  本文關(guān)鍵詞：dijkstra算法，由筆耕文化傳播整理發(fā)布。