C/C++最短路徑算法之迪杰斯特拉Dijkstra的實現(xiàn)詳解
前言
我們在生活中常常面臨對路徑選擇的決策問題，這就要用到最短路徑的算法了。
對于我這種榆木腦袋，顯然迪杰斯特拉的這種算法有點高深。主要是我笨。
對于網(wǎng)圖來說，最短路徑，就是指兩個頂點之間經(jīng)過的邊上權(quán)值之和最小的路徑，并且我們稱路徑上的第一個頂點就是源點，最后一個頂點式終點。
一、迪杰斯特拉（Dijkstra）算法是什么
迪杰斯特拉算法是一個按照路徑長度遞增的次序產(chǎn)生最短路徑的算法。
二、實現(xiàn)步驟
1.算法思路
這里先采用鄰接表來遍歷。
在遍歷節(jié)點時，找到未遍歷節(jié)點中權(quán)值最小的進行遍歷，并且及時更新最短路徑長度dist數(shù)組[]。
首先設(shè)置path[]數(shù)組代表路徑信息。 dist[] 表示最短路徑長度。
int* path = (int*)malloc(sizeof(G.vexnum)); int* dist = (int*)malloc(sizeof(G.vexnum));
2.進入主函數(shù)ShortestPath()
1.創(chuàng)建final數(shù)組并且初始化path[]、dist[]數(shù)組
final數(shù)組來表示是否完成對該節(jié)點的最短路徑求解。final[v]==1表示完成最短路徑搜素，反之final[vi]==0表示未完成。
在算法中只有在求得最短路徑后才會將final[vi]置為1，也可以簡單理解為訪問標(biāo)志數(shù)組。
path數(shù)組全體初始化為0。
final數(shù)組因為最開始并沒有完成最短路徑求解，故置為0。
dist數(shù)組初始化為與vi相連的節(jié)點的權(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é)點的初始化
在遍歷vi節(jié)點時，vi到vi的路徑為0，vi到vi之間也不需要求路徑，故dist[vi]=0;final[vi]=1;
dist[vi] = 0; final[vi] = 1;
肯定有人問，那path呢，path代表路徑信息，vi時源點自然就是0了，當(dāng)然初始化時也可以把path全初始化為-1，看個人習(xí)慣了。
3.進入主循環(huán)
將對刨掉源點的其他節(jié)點進行遍歷，故外循環(huán)次數(shù)為g.vexnum-1次。
再在dist數(shù)組中找到權(quán)值最小并且未完成最短路徑搜索的節(jié)點，用k來表示該節(jié)點下標(biāo)。
其次找到最小權(quán)值k節(jié)點后，設(shè)置final[k]=1，再對k節(jié)點進行遍歷，更新dist和path數(shù)組。
更新方法：若與k節(jié)點相連的節(jié)點未完成最短路徑搜索并且k節(jié)點權(quán)值+該節(jié)點權(quán)值小于dist數(shù)組中的源點到該節(jié)點的最短路徑，那么將更新dist數(shù)組中到該節(jié)點的最短路徑，并且更新path數(shù)組，到該節(jié)點的前驅(qū)為k節(jié)點。
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;
}五、測試代碼（鄰接表下）
這里就測試一個鄰接表下的。
自己花了個圖
因為我的邊表建立的時候A是第一個，自然A就是源點。
結(jié)果如下
很完美。
總結(jié)
很顯然這個算法的時間復(fù)雜度是O(n²)，如果要知道任意頂點到其余所有頂點的最短路徑，那么就可以對每一個頂點當(dāng)作源點進行一次迪杰斯特拉算法。這時候后整個算法的時間復(fù)雜度也就成了O(n³)。這個和弗洛伊德算法的時間復(fù)雜度一樣，但弗洛伊德算法那是相當(dāng)?shù)膬?yōu)雅。
到此這篇關(guān)于C/C++最短路徑算法之迪杰斯特拉Dijkstra的實現(xiàn)詳解的文章就介紹到這了,更多相關(guān)C/C++迪杰斯特拉內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++實現(xiàn)LeetCode(174.地牢游戲),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語言使用Bresenham算法生成直線（easyx圖形庫）
這篇文章主要為大家詳細(xì)介紹了C語言使用Bresenham算法生成直線，基于easyx圖形庫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了C++類中的static和const用法,是C++面向?qū)ο蟪绦蛟O(shè)計中非常重要的概念,需要的朋友可以參考下2014-08-08
詳解C++中虛析構(gòu)函數(shù)的作用及其原理分析
這篇文章主要介紹了C++中虛析構(gòu)函數(shù)的作用及其原理分析，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
最近在做項目時經(jīng)常需要獲得文件的大小操作，雖然在網(wǎng)絡(luò)上已經(jīng)有許多篇博客介紹了，但是還是想總結(jié)出自己一篇，記錄一下自己在項目中是怎么獲得文件大小的2022-10-10
這篇文章主要介紹了C語言結(jié)構(gòu)體使用之鏈表，下面文章主要圍繞結(jié)構(gòu)體的概念和用法、結(jié)構(gòu)體數(shù)組和結(jié)構(gòu)體指針、包含結(jié)構(gòu)體的結(jié)構(gòu)體、結(jié)構(gòu)體搭建鏈表方法、結(jié)構(gòu)體及鏈表在產(chǎn)品應(yīng)用場景等多個主題展開鏈表的相關(guān)資料，需要的小伙伴可以參考一下2022-03-03
這篇文章主要為大家詳細(xì)介紹了基于C語言實現(xiàn)三子棋小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要介紹了C中二叉樹的建立和各種遍歷實例代碼，涉及樹節(jié)點的定義，后序遍歷，層序遍歷，深度優(yōu)先和廣度優(yōu)先等相關(guān)內(nèi)容，具有一定借鑒價值,需要的朋友可以參考下2021-07-07
C++最短路徑Dijkstra算法的分析與具體實現(xiàn)詳解
經(jīng)典的求解最短路徑算法有這么幾種：廣度優(yōu)先算法、Dijkstra算法、Floyd算法。本文是對?Dijkstra算法的總結(jié)，該算法適用于帶權(quán)有向圖，可求出起始頂點到其他任意頂點的最小代價以及對應(yīng)路徑，希望對大家有所幫助2023-03-03
這篇文章主要介紹了C語言關(guān)鍵字union的定義和使用詳解,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-02-02