前言

迪杰斯特拉(Dijkstra)算法是由荷蘭計算機科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有權(quán)圖中單源最短路徑問題。迪杰斯特拉算法主要特點是從起始點開始，采用貪心算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接節(jié)點，直到擴展到終點為止。

不太懂的可以看視頻 QWQ? （來著@Abel）

算法實現(xiàn)：

1. 定義一個數(shù)組dist[]，dist[i]表示從起點到頂點i的最短路徑長度，初始化為無窮大，dist[s]=0，其中s為起點。
2. 定義一個數(shù)組visited[]，visited[i]表示頂點i是否已經(jīng)被標記為已確定最短路徑的頂點，初始化為false。
3. 從dist[]中找到當(dāng)前未被標記的dist[i]最小的頂點u，標記visited[u]=true。
4. 遍歷所有與u相鄰的頂點v，如果visited[v]=false，且從起點到u再到v的路徑長度小于dist[v]，則更新dist[v]=dist[u]+w(u,v)，其中w(u,v)為邊(u,v)的權(quán)值。

重復(fù)步驟3和步驟4，直到所有頂點都被標記為已確定最短路徑的頂點。

以下是求無向網(wǎng)（儲存方式為鄰接矩陣）中起點s到各點的最短路徑的代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#define MVNum 100//最大頂點數(shù)
#define MaxInt 66666//表示極大值
typedef struct {
	char vexs[MVNum];//頂點表（頂點為字符型）
	int arcs[MVNum][MVNum];//鄰接矩陣（權(quán)值為整型）
	int vexnum, arcnum;//圖的當(dāng)前點數(shù)和邊數(shù)
}AMGraph;

//定位
int LocateVex(AMGraph* G, char v) {
	int i;
	for (i = 0; i < G->vexnum; i++) {
		if (G->vexs[i] == v) {
			return i;
		}
	}
	return -1;
}

//無向網(wǎng)的建立
AMGraph* CreateUDN() {
	int i, j, k, w;
	char v1, v2;
	AMGraph* G = malloc(sizeof(AMGraph));
	printf("輸入總頂點數(shù)，邊數(shù)\n");
	scanf("%d%d", &G->vexnum, &G->arcnum);
	getchar();//吸收換行符
	printf("依次輸入點的信息\n");
	for (i = 0; i < G->vexnum; i++) {
		scanf("%c", &G->vexs[i]);
	}
	getchar();//吸收換行符
	for (i = 0; i < G->vexnum; i++)
		for (j = 0; j < G->vexnum; j++) {
			if (i == j) {
				G->arcs[i][j] = 0;
			}
			else {
				G->arcs[i][j] = MaxInt;
			}
		}
	for (k = 0; k < G->arcnum; k++) {
		printf("輸入一條邊依附的頂點及權(quán)值\n");
		scanf("%c%c", &v1, &v2);
		scanf("%d", &w);
		getchar();//吸收換行符
		i = LocateVex(G, v1), j = LocateVex(G, v2);//確定v1、v2在頂點數(shù)組的下標
		G->arcs[i][j] = w;//邊<v1,v2>權(quán)值置為w
		G->arcs[j][i] = w;//無向網(wǎng)對稱邊<v2,v2>權(quán)值也置為w
	}
	return G;
}

//輸出鄰接矩陣
void print(AMGraph* G) {
	int i, j;
	printf("  ");
	for (i = 0; i < G->vexnum; i++) {
		printf("%c ", G->vexs[i]);
	}
	printf("\n");
	for (i = 0; i < G->vexnum; i++) {
		printf("%c ", G->vexs[i]);
		for (j = 0; j < G->vexnum; j++) {
			if (G->arcs[i][j] == MaxInt)
				printf("∞ ");
			else
				printf("%d ", G->arcs[i][j]);
		}
		printf("\n");
	}
}

//迪杰斯特拉算法
void Dijkstra(AMGraph* G, int s) {
	int dist[MVNum];//用來儲存各頂點與起點的距離
	bool visited[MVNum];//用來標記已確定最短路徑的頂點
	int i, j, k, u, min;
	//初始化數(shù)組dist與visited
	for (i = 0; i < G->vexnum; i++) {
		dist[i] = MaxInt;
		visited[i] = false;
	}
	dist[s] = 0;//起始點s最短距離為0
	//每次循環(huán)會標記一個頂點u，直到所有頂點被標記（循環(huán)次數(shù)就是頂點數(shù)-1，起點已找到最短路徑0）
	for (k = 1; k < G->vexnum; k++) {
		min = MaxInt;
		//找到當(dāng)前未被標記的距離起點最近的頂點u
		for (i = 0; i < G->vexnum; i++) {
			if (dist[i] < min && !visited[i]) {
				u = i;
				min = dist[i];
			}
		}
		visited[u] = true;//標記頂點u
		/*遍歷頂點u的鄰結(jié)點，當(dāng) dist[u] + G->arcs[u][j] < dist[j]時
		（頂點u距離起點s的長度dist[u]加上頂點u與鄰接點j的距離G->arcs[u][j]小于頂點j距離起點s的距離dist[j]），
		更新頂點j距離起點的路徑長度*/
		for (j = 0; j < G->vexnum; j++) {
			if (!visited[j] && dist[u] + G->arcs[u][j] < dist[j]) {
				dist[j] = dist[u] + G->arcs[u][j];
			}
		}
	}
	//輸出結(jié)果
	for (i = 0; i < G->vexnum; i++) {
		printf("起點%c到頂點%c的最短路徑為：%d\n", G->vexs[s], G->vexs[i], dist[i]);
	}
}

int main() {
	AMGraph* G = CreateUDN();
	printf("該無向網(wǎng)鄰接矩陣為：\n");
	print(G);
	Dijkstra(G, 0);
}

若頂點數(shù)為n，求解最短路徑的主循環(huán)共進行n-1次，每次執(zhí)行的時間為，所以算法時間復(fù)雜度為。

示例：

求如下圖所示v0到各點的最短路徑

?運行結(jié)果如下：

A、B、C······代替v0、v1、v2······

總結(jié)

如果是有向網(wǎng)或者是以鄰接表方式儲存的有權(quán)圖，算法實現(xiàn)流程還是一樣的，只不過代碼上大同小異。文章來源地址http://www.zghlxwxcb.cn/news/detail-770475.html

到了這里，關(guān)于C語言 最短路徑 迪杰斯特拉（Dijkstra）算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！