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