C/C++最短路徑算法之迪杰斯特拉Dijkstra的實(shí)現(xiàn)詳解
前言
我們在生活中常常面臨對路徑選擇的決策問題，這就要用到最短路徑的算法了。
對于我這種榆木腦袋，顯然迪杰斯特拉的這種算法有點(diǎn)高深。主要是我笨。
對于網(wǎng)圖來說，最短路徑，就是指兩個頂點(diǎn)之間經(jīng)過的邊上權(quán)值之和最小的路徑，并且我們稱路徑上的第一個頂點(diǎn)就是源點(diǎn)，最后一個頂點(diǎn)式終點(diǎn)。
一、迪杰斯特拉（Dijkstra）算法是什么
迪杰斯特拉算法是一個按照路徑長度遞增的次序產(chǎn)生最短路徑的算法。
二、實(shí)現(xiàn)步驟
1.算法思路
這里先采用鄰接表來遍歷。
在遍歷節(jié)點(diǎn)時，找到未遍歷節(jié)點(diǎn)中權(quán)值最小的進(jìn)行遍歷，并且及時更新最短路徑長度dist數(shù)組[]。
首先設(shè)置path[]數(shù)組代表路徑信息。 dist[] 表示最短路徑長度。
int* path = (int*)malloc(sizeof(G.vexnum)); int* dist = (int*)malloc(sizeof(G.vexnum));
2.進(jìn)入主函數(shù)ShortestPath()
1.創(chuàng)建final數(shù)組并且初始化path[]、dist[]數(shù)組
final數(shù)組來表示是否完成對該節(jié)點(diǎn)的最短路徑求解。final[v]==1表示完成最短路徑搜素，反之final[vi]==0表示未完成。
在算法中只有在求得最短路徑后才會將final[vi]置為1，也可以簡單理解為訪問標(biāo)志數(shù)組。
path數(shù)組全體初始化為0。
final數(shù)組因?yàn)樽铋_始并沒有完成最短路徑求解，故置為0。
dist數(shù)組初始化為與vi相連的節(jié)點(diǎn)的權(quán)值，沒連就是INFINITY（65535）。
int* final = (int*)malloc(sizeof(int) * g.vexnum);
for (int i = 0; i < g.vexnum; i++) {
path[i] = 0;
final[i] = 0;
dist[i] = INFNITY;
}
ArcNode* p = g.vertexlist[vi].firstarc;
for (p; p != NULL; p = p->nextarc) {
dist[p->adjvex] = p->weight;
}2.對于節(jié)點(diǎn)的初始化
在遍歷vi節(jié)點(diǎn)時，vi到vi的路徑為0，vi到vi之間也不需要求路徑，故dist[vi]=0;final[vi]=1;
dist[vi] = 0; final[vi] = 1;
肯定有人問，那path呢，path代表路徑信息，vi時源點(diǎn)自然就是0了，當(dāng)然初始化時也可以把path全初始化為-1，看個人習(xí)慣了。
3.進(jìn)入主循環(huán)
將對刨掉源點(diǎn)的其他節(jié)點(diǎn)進(jìn)行遍歷，故外循環(huán)次數(shù)為g.vexnum-1次。
再在dist數(shù)組中找到權(quán)值最小并且未完成最短路徑搜索的節(jié)點(diǎn)，用k來表示該節(jié)點(diǎn)下標(biāo)。
其次找到最小權(quán)值k節(jié)點(diǎn)后，設(shè)置final[k]=1，再對k節(jié)點(diǎn)進(jìn)行遍歷，更新dist和path數(shù)組。
更新方法：若與k節(jié)點(diǎn)相連的節(jié)點(diǎn)未完成最短路徑搜索并且k節(jié)點(diǎn)權(quán)值+該節(jié)點(diǎn)權(quán)值小于dist數(shù)組中的源點(diǎn)到該節(jié)點(diǎn)的最短路徑，那么將更新dist數(shù)組中到該節(jié)點(diǎn)的最短路徑，并且更新path數(shù)組，到該節(jié)點(diǎn)的前驅(qū)為k節(jié)點(diǎn)。
int k;
for (int v = 1; v < g.vexnum; v++) {
int min = INFNITY;
for (int w = 0; w < g.vexnum; w++) {
if (!final[w] && dist[w] < min) {
k = w;
min = dist[w];
}
}
final[k] = 1;
ArcNode* p = g.vertexlist[k].firstarc;
while (p != NULL) {
if (!final[p->adjvex] && (p->weight + min) < dist[p->adjvex]) {
dist[p->adjvex] = min + p->weight;
path[p->adjvex] = k;
}
p = p->nextarc;
}
}三、全部代碼（鄰接表下）
void ShortestPath(AdjList g, int vi, int* path, int* dist) {
int* final = (int*)malloc(sizeof(int) * g.vexnum);
for (int i = 0; i < g.vexnum; i++) {
path[i] = 0;
final[i] = 0;
dist[i] = INFNITY;
}
ArcNode* p = g.vertexlist[vi].firstarc;
for (p; p != NULL; p = p->nextarc) {
dist[p->adjvex] = p->weight;
}
dist[vi] = 0;
final[vi] = 1;
int k;
for (int v = 1; v < g.vexnum; v++) {
int min = INFNITY;
for (int w = 0; w < g.vexnum; w++) {
if (!final[w] && dist[w] < min) {
k = w;
min = dist[w];
}
}
final[k] = 1;
ArcNode* p = g.vertexlist[k].firstarc;
while (p != NULL) {
if (!final[p->adjvex] && (p->weight + min) < dist[p->adjvex]) {
dist[p->adjvex] = min + p->weight;
path[p->adjvex] = k;
}
p = p->nextarc;
}
}
free(final);
return;
}四、全部代碼（鄰接矩陣下）
思路大同小異，在初始化時有些不同，其他很相像。
void ShortestPath(AdjMatrix g, int vi, int* path, int* dist) {
int* final = (int*)malloc(sizeof(int) * g.vexnum);
for (int i = 0; i < g.vexnum; i++) {
path[i] = 0;
final[i] = 0;
dist[i] = g.arc[vi][i];
}
dist[vi] = 0;
final[vi] = 1;
int k;
for (int v = 1; v < g.vexnum; v++) {
int min = INFNITY;
for (int w = 0; w < g.vexnum; w++) {
if (!final[w] && dist[w] < min) {
k = w;
min = dist[w];
}
}
final[k] = 1;
ArcNode* p = g.vertexlist[k].firstarc;
for (int w = 0; w < g.vexnum; w++) {
if (!final[w] && (min+g.arc[k][w])<dist[w]) {
dist[w]=min+g.arc[k][w];
path[w]=k;
}
}
}
free(final);
return;
}五、測試代碼（鄰接表下）
這里就測試一個鄰接表下的。
自己花了個圖
因?yàn)槲业倪叡斫⒌臅r候A是第一個，自然A就是源點(diǎn)。
結(jié)果如下
很完美。
總結(jié)
很顯然這個算法的時間復(fù)雜度是O(n²)，如果要知道任意頂點(diǎn)到其余所有頂點(diǎn)的最短路徑，那么就可以對每一個頂點(diǎn)當(dāng)作源點(diǎn)進(jìn)行一次迪杰斯特拉算法。這時候后整個算法的時間復(fù)雜度也就成了O(n³)。這個和弗洛伊德算法的時間復(fù)雜度一樣，但弗洛伊德算法那是相當(dāng)?shù)膬?yōu)雅。
到此這篇關(guān)于C/C++最短路徑算法之迪杰斯特拉Dijkstra的實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)C/C++迪杰斯特拉內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
64位linux 編譯c提示gnu/stubs-32.h:No such file or directory的解決方法
這篇文章主要介紹了64位linux 編譯c提示gnu/stubs-32.h:No such file or directory的解決方法,需要的朋友可以參考下2020-03-03
本文主要介紹了C語言中return返回函數(shù)局部變量的問題，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
本文主要介紹了C語言#define預(yù)處理宏定義，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
這篇文章主要為大家詳細(xì)介紹了C語言數(shù)字圖像處理之直方圖均衡化，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
這篇文章主要介紹了基于VS2019配置opencv4.0的方法步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
這篇文章主要介紹了C/C++常用函數(shù)易錯點(diǎn)分析,包含了memset、sizeof、getchar三個常用函數(shù)的分析,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細(xì)介紹了利用C語言實(shí)現(xiàn)五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
Qt QChart 創(chuàng)建圖表的實(shí)現(xiàn)方法
這篇文章主要介紹了Qt QChart 創(chuàng)建圖表的實(shí)現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
Qt?加載?libjpeg?庫出現(xiàn)“長跳轉(zhuǎn)已經(jīng)運(yùn)行”錯誤問題解決
這篇文章主要介紹了Qt?加載?libjpeg?庫出現(xiàn)“長跳轉(zhuǎn)已經(jīng)運(yùn)行”錯誤,本文給大家分享完美解決方案，需要的朋友可以參考下2023-04-04
這篇文章主要介紹了C++ 面試題翻譯電話號碼實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-04-04