日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

C/C++最短路徑算法之迪杰斯特拉Dijkstra的實現(xiàn)詳解_C 語言

作者：菠菠蘿寶 ? 更新時間： 2022-09-19 編程語言

前言

我們在生活中常常面臨對路徑選擇的決策問題，這就要用到最短路徑的算法了。

對于我這種榆木腦袋，顯然迪杰斯特拉的這種算法有點高深。主要是我笨。

對于網(wǎng)圖來說，最短路徑，就是指兩個頂點之間經(jīng)過的邊上權(quán)值之和最小的路徑，并且我們稱路徑上的第一個頂點就是源點，最后一個頂點式終點。

一、迪杰斯特拉（Dijkstra）算法是什么

迪杰斯特拉算法是一個按照路徑長度遞增的次序產(chǎn)生最短路徑的算法。

二、實現(xiàn)步驟

1.算法思路

這里先采用鄰接表來遍歷。

在遍歷節(jié)點時，找到未遍歷節(jié)點中權(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é)點的最短路徑求解。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.進(jìn)入主循環(huán)

將對刨掉源點的其他節(jié)點進(jìn)行遍歷，故外循環(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é)點進(jìn)行遍歷，更新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(n2)，如果要知道任意頂點到其余所有頂點的最短路徑，那么就可以對每一個頂點當(dāng)作源點進(jìn)行一次迪杰斯特拉算法。這時候后整個算法的時間復(fù)雜度也就成了O(n3)。這個和弗洛伊德算法的時間復(fù)雜度一樣，但弗洛伊德算法那是相當(dāng)?shù)膬?yōu)雅。

原文鏈接：https://blog.csdn.net/qq_45400167/article/details/125982074

欄目分類
最近更新