基本思想

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

此外，引進(jìn)兩個(gè)集合S和U。S的作用是記錄已求出最短路徑的頂點(diǎn)(以及相應(yīng)的最短路徑長(zhǎ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中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑。 然后，再?gòu)腢中找出路徑最短的頂點(diǎn)，并將其加入到S中；接著，更新U中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑。 … 重復(fù)該操作，直到遍歷完所有頂點(diǎn)

操作步驟

(1) 初始時(shí)，S只包含起點(diǎn)s；U包含除s外的其他頂點(diǎn)，且U中頂點(diǎn)的距離為”起點(diǎn)s到該頂點(diǎn)的距離”[例如，U中頂點(diǎn)v的距離為(s,v)的長(zhǎng)度，然后s和v不相鄰，則v的距離為∞]。

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

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

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

實(shí)現(xiàn)

// 鄰接矩陣 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是鄰接矩陣對(duì)應(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是鄰接矩陣邊對(duì)應(yīng)的結(jié)構(gòu)體。

迪杰斯特拉算法

/** Dijkstra最短路徑。* 即，統(tǒng)計(jì)圖(G)中"頂點(diǎn)vs"到其它各個(gè)頂點(diǎn)的最短路徑。** 參數(shù)說(shuō)明：* G -- 圖* vs -- 起始頂點(diǎn)(start vertex)。即計(jì)算"頂點(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"之前的那個(gè)頂點(diǎn)。* dist -- 長(zhǎng)度數(shù)組。即，dist[i]是"頂點(diǎn)vs"到"頂點(diǎn)i"的最短路徑的長(zhǎng)度。*/ 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的最短路徑還沒(mé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)。}// 對(duì)"頂點(diǎn)vs"自身進(jìn)行初始化flag[vs] = 1;dist[vs] = 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 (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]); }

references

Dijkstra算法(一)之 C語(yǔ)言詳解 - 如果天空不死 - 博客園

總結(jié)

以上是生活随笔為你收集整理的数据结构之Dijkstra算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。