前言

我們?cè)谏钪谐３Ｃ媾R對(duì)路徑選擇的決策問(wèn)題，這就要用到最短路徑的算法了。

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

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

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

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

二、實(shí)現(xiàn)步驟

1.算法思路

這里先采用鄰接表來(lái)遍歷。

在遍歷節(jié)點(diǎn)時(shí)，找到未遍歷節(jié)點(diǎn)中權(quán)值最小的進(jìn)行遍歷，并且及時(shí)更新最短路徑長(zhǎng)度dist數(shù)組[]。

首先設(shè)置path[]數(shù)組代表路徑信息。 dist[] 表示最短路徑長(zhǎng)度。

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ù)組來(lái)表示是否完成對(duì)該節(jié)點(diǎn)的最短路徑求解。final[v]==1表示完成最短路徑搜素，反之final[vi]==0表示未完成。

在算法中只有在求得最短路徑后才會(huì)將final[vi]置為1，也可以簡(jiǎn)單理解為訪問(wèn)標(biāo)志數(shù)組。

path數(shù)組全體初始化為0。

final數(shù)組因?yàn)樽铋_(kāi)始并沒(méi)有完成最短路徑求解，故置為0。

dist數(shù)組初始化為與vi相連的節(jié)點(diǎn)的權(quán)值，沒(méi)連就是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.對(duì)于節(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;

肯定有人問(wèn)，那path呢，path代表路徑信息，vi時(shí)源點(diǎn)自然就是0了，當(dāng)然初始化時(shí)也可以把path全初始化為-1，看個(gè)人習(xí)慣了。

3.進(jìn)入主循環(huán)

將對(duì)刨掉源點(diǎn)的其他節(jié)點(diǎn)進(jìn)行遍歷，故外循環(huán)次數(shù)為g.vexnum-1次。

再在dist數(shù)組中找到權(quán)值最小并且未完成最短路徑搜索的節(jié)點(diǎn)，用k來(lái)表示該節(jié)點(diǎn)下標(biāo)。

其次找到最小權(quán)值k節(jié)點(diǎn)后，設(shè)置final[k]=1，再對(duì)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;
}

五、測(cè)試代碼（鄰接表下）

這里就測(cè)試一個(gè)鄰接表下的。

自己花了個(gè)圖

因?yàn)槲业倪叡斫⒌臅r(shí)候A是第一個(gè)，自然A就是源點(diǎn)。

結(jié)果如下

很完美。

總結(jié)

很顯然這個(gè)算法的時(shí)間復(fù)雜度是O(n²)，如果要知道任意頂點(diǎn)到其余所有頂點(diǎn)的最短路徑，那么就可以對(duì)每一個(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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論