? ? ? ?目錄

一、什么是最短路徑

二、迪杰斯特拉（Dijkstra）算法

?三、應(yīng)用Dijkstra算法

（1） Dijkstra算法函數(shù)分析

????????求圖的最短路徑在實(shí)際生活中有許多應(yīng)用，比如說在你在一個(gè)景區(qū)的某個(gè)景點(diǎn)，參觀完后，要怎么走最少的路程到你想?yún)⒂^的下個(gè)景點(diǎn)，這就利用到了求圖最短路徑的算法。求圖的最短路徑有很多算法，這里介紹一種迪杰斯特拉（Dijkstra）算法來求圖的最短路徑。

? ? ? ? 在介紹算法前，需要掌握一點(diǎn)圖的基本知識(shí)，比如說什么是路徑，什么是路徑長(zhǎng)度等。如果對(duì)這些不了解的話，建議先了解一下。

? ? ? ? 這是我寫的一篇博客，對(duì)圖的一些基本知識(shí)的簡(jiǎn)介——圖的一些基本知識(shí)。

一、什么是最短路徑

? ? ? ? 在網(wǎng)圖和非網(wǎng)圖中，最短路徑的含義是不同的。由于非網(wǎng)圖沒有邊上的權(quán)值，所謂最短路徑，其實(shí)指的就是兩個(gè)頂點(diǎn)之間經(jīng)過的邊數(shù)最少的路勁（即可以理解為把每一條邊的權(quán)值看作是1）。

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

? ? ? ? 求帶權(quán)有向圖G的最短路徑問題一般可分為兩類：一是單源最短路徑，即求圖中某一個(gè)頂點(diǎn)到其它頂點(diǎn)的最短路徑，可以通過經(jīng)典的 Dijkstra（迪杰斯特拉）算法求解（即是我要介紹的算法）；二是求每對(duì)頂點(diǎn)間的最短路徑，可通過Floyd（弗洛伊德）算法來求解。

二、迪杰斯特拉（Dijkstra）算法

? ? ? ? Dijkstra算法算法思路是設(shè)置一個(gè)集合S記錄已求得的最短路徑的頂點(diǎn)，初始時(shí)把源點(diǎn)V0（圖中的某個(gè)頂點(diǎn)）放入S，集合S每并入一個(gè)新頂點(diǎn) V，都要修改源點(diǎn)V0到集合 V-S 中頂點(diǎn)當(dāng)前的最短路徑長(zhǎng)度值（這里可能大家會(huì)很懵，但等會(huì)我會(huì)用一個(gè)例子來解說）。

? ? ? ? 在構(gòu)造過程中需要兩個(gè)輔助數(shù)組：

• dist[ ] ：記錄從源點(diǎn)V0到其他各頂點(diǎn)當(dāng)前的最短路徑長(zhǎng)度，它的初態(tài)為：若從 V0 到 V?有直接路徑（即V0 和 V?鄰接），則dist[ i ]為這兩個(gè)頂點(diǎn)邊上的權(quán)值；否則置 dist[ i ]?為?∞。
• path[ ]：path[ i ]表示從源點(diǎn)到頂點(diǎn) i 之間的最短路徑的前驅(qū)結(jié)點(diǎn)。在算法結(jié)束時(shí)，可以根據(jù)其值追溯到源點(diǎn) V0 到 V?的最短路徑。

? ? ? ? 假設(shè)從頂點(diǎn) V0 = 0出發(fā)，鄰接矩陣Edge表示帶權(quán)無向圖，Edge[i][j]表示無向邊 (i, j)的權(quán)值，若不存在無向邊(i, j)，則Edge[i][]為?∞。

? ? ? ? Dijkstra算法步驟如下：

1）初始化：集合S初始化為{0}，dist[ ] 的初始值dist[i] = Edge[0][i]，path[ ]的初始值path[i] = -1，i = 1,2,...,n-1。

2）從頂點(diǎn)集合 V - S中選出V，滿足dist[j] = Min{dist[i] | V??V - S}，V就是當(dāng)前求的一條從 V0 出發(fā)的最短路徑的終點(diǎn)，令S = S{j}。

3）修改從V0出發(fā)到集合 V - S上任一頂點(diǎn) V?可達(dá)的最短路徑長(zhǎng)度：若

??????dist[j] + Edge[j][k] < dist[k]，則更新 dist[k] = dist[j] + Edge[j][k]，并修改path[k] = j（即修改頂點(diǎn)V的最短路徑的前驅(qū)結(jié)點(diǎn) ）??。

4）重復(fù) 2）~? 3）操作共 n-1 次，直到所有的頂點(diǎn)都包含在 S 中。

解釋下步驟3），每當(dāng)一個(gè)頂點(diǎn)加入S后，可能需要修改源點(diǎn)V0 到集合 V-S中的可達(dá)頂點(diǎn)當(dāng)前的最短路徑長(zhǎng)度。下面舉一個(gè)例子。如下圖所示，源點(diǎn)為V0，初始時(shí)S = {V0}，dist[1] = 6, dist[2] = 3,當(dāng)V并入集合S后，dist[1] 需要更新為 5（其比6小，即說明兩點(diǎn)之間不是直線最短，要根據(jù)兩點(diǎn)之間路徑的權(quán)值之和來看）。

下面來講解利用Dijkstra算法來求下圖中的頂點(diǎn) 0 出發(fā)至其余頂點(diǎn)的最短路徑的過程。

初始化：集合S初始化為{V}，V可達(dá)V和V，其余頂點(diǎn)不可達(dá)，因此dist[]數(shù)組和path[]數(shù)組的設(shè)置如下：

第一輪：選出最小dist[2]，將頂點(diǎn) V?并入集合S，此時(shí)已找到 V?到 V?的最短路徑，S = {V，V}。當(dāng) V?加入到S后，從V到集合V-S中可到達(dá)頂點(diǎn)的最短路徑長(zhǎng)度可能會(huì)產(chǎn)生變化。因此需要更新dist[]數(shù)組。V可達(dá)V，因V?-> V?-> V的距離 5 比 dist[1] = 6小，更新dist[1] = 5，并修改?path[1] = 2（即V的最短路徑的前驅(qū)為V）；V?可達(dá) V，V?-> V?- > V的距離 8 比 dist[3] =?∞ 小，更新dist[3] = 8，path[3] = 2；V可達(dá)V，V?-> V?-> V?的距離 10 小于 dist[5] =?∞，更新dist[5] = 10，path[5] = 2。V再無到達(dá)其余的頂點(diǎn)的路徑，結(jié)束這一輪，此時(shí)dist[]數(shù)組和path[]數(shù)組如下：

?第二輪：選出最小值dist[1]，將頂點(diǎn) V?并入集合S，此時(shí)已找到 V?到 V?的最短路徑，S = {V,V，V}。然后更新dist[]數(shù)組和path[]數(shù)組，V可達(dá)V，V?-> V?-> V?-> V?的距離 6 小于 dist [3] = 8 ，更新 dist[3] = 6，path[3] = 1；V?可達(dá) V，但V已經(jīng)在集合S中，故不進(jìn)行操作；V?可達(dá) V，?V?-> V?-> V?->?V的距離 9 小于 dist[4]?=?∞，更新dist[4] = 9，path[4] = 1。V?已無到達(dá)其余頂點(diǎn)的路徑，結(jié)束此輪，此時(shí)dist[]數(shù)組和path[]數(shù)組如下：

第三輪： 選出最小值 dist[3]，將頂點(diǎn) V?并入集合 S，此時(shí)已找到 V?到 V?的最短路徑，S = {?V,V，V，V}。接著更新dist[]數(shù)組和path[]數(shù)組，V?可到達(dá) V，?V?-> V?-> V?-> V?-> V?的距離為 9 等于 dist[4] = 9，我們不做更新；V?可到達(dá) V，??V?-> V?-> V?-> V?->?V?的距離為 12 大于 dist[5] = 10，不做更新。?V?再無達(dá)到其余頂點(diǎn)的路徑，結(jié)束此輪，此時(shí)dist[]數(shù)組和path[]數(shù)組如下：

第四輪：選出最小值 dist[4]，將頂點(diǎn) V?并入集合 S，此時(shí)已找到 V?到 V的最短路徑，S = {?V,V，V，V，V}。繼續(xù)更新dist[]數(shù)組和path[]數(shù)組，V可到 V，?V?-> V?-> V?->?V?-> V的距離 11 小于 dist[5] = 10，故不進(jìn)行更新操作；V?可到 V，?V?-> V?-> V?->?V?->?V的距離 11 小于 dist[6] =?∞，更新 dist[6] = 11，path[6] = 4。V?再無達(dá)到其余頂點(diǎn)的路徑，結(jié)束此輪，此時(shí)dist[]數(shù)組和path[]數(shù)組如下：

第五輪：?選出最小值 dist[5]，將頂點(diǎn) V?并入集合S，此時(shí)已找到 V?到 V的最短路徑，S =??{?V,V，V，V，V，V}。然后ist[]數(shù)組和path[]數(shù)組，V?可到 V，?V?-> V?-> V?-> V?的最短路徑 13 大于 dist[6]，故不進(jìn)行更新操作。V?再無達(dá)到其余頂點(diǎn)的路徑，結(jié)束此輪，此時(shí)dist[]數(shù)組和path[]數(shù)組如下：?

?第六輪：選出最小值 dist[6]，將頂點(diǎn) V?并入集合，此時(shí)全部頂點(diǎn)都已包含在S中，結(jié)束算法。

?整個(gè)算法每一輪的結(jié)果如下：?

總結(jié)：Dijkstra算法就是最開始選離源點(diǎn)V最近的點(diǎn)，然后選好點(diǎn)后，再從選好點(diǎn)的看其鄰接點(diǎn)的距離dist[]是否減小，減小就修改dist[]和path[]；否則就不進(jìn)行修改操作。Dijkstra算法基于貪心策略，用鄰接矩陣表示圖時(shí)，來使用Dijkstra算法，其時(shí)間復(fù)雜度為O(n*n)。當(dāng)邊上帶有負(fù)權(quán)值時(shí)，Dijkstra算法并不適用。

使用dist[]數(shù)組和path[]數(shù)組，求最短路徑，這里介紹一個(gè)例子，其它頂點(diǎn)依次類推。

V到V的最短路徑，先利用dist[6] = 11 得出?V到V的距離，然后利用path[]得出路徑。path[6] = 4，頂點(diǎn)V的前驅(qū)頂點(diǎn)是 V，再由 path[4] = 1,表示 V?的前驅(qū)是 V?, path[1] = 2，表示 V?的前驅(qū)是 V，path[2] = -1，結(jié)束。最后可以得到 V?到 V?的最短路徑為 V?<- V?<- V?<- V?<- V，即?V?-> V?-> V?->?V?->?V?。

?三、應(yīng)用Dijkstra算法

? ? ? ? 理解上面的Dijkstra算法求最短路徑的過程，那么下面的應(yīng)用Dijkstra算法的程序就很容易理解。此程序分三大塊，在程序末尾我會(huì)來粗略介紹下。

使用此程序需輸入以下內(nèi)容創(chuàng)建圖G：

第一步：7 12

第二步：0123456

第三步：依次輸入下面的內(nèi)容，輸入完一行就按下?lián)Q行鍵

0 1 6

0 2 3

1 2 2

1 3 1

1 4 4

2 3 5

2 5 7

3 4 3

3 5 6

4 5 2

4 6 2

5 6 3

? ? ? ? 上面輸入完后，即可創(chuàng)建下面的圖G：?

/*
使用此程序需輸入以下內(nèi)容創(chuàng)建圖G：
第一步：7 12
第二步：0123456
第三步：依次輸入下面的內(nèi)容，輸入完一行就按下?lián)Q行鍵
0 1 6
0 2 3
1 2 2
1 3 1
1 4 4
2 3 5
2 5 7
3 4 3
3 5 6
4 5 2
4 6 2
5 6 3
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MaxVerterNum 100		// 頂點(diǎn)數(shù)目的最大值
#define INFINITY 65535			// 用65535代表 ∞

typedef char VertexType;		// 頂點(diǎn)的數(shù)據(jù)類型
typedef int EdgeType;			// 帶權(quán)圖中邊上權(quán)值的數(shù)據(jù)類型

/* 鄰接矩陣的存儲(chǔ)結(jié)構(gòu) */
typedef struct
{
	VertexType Vexs[MaxVerterNum];					// 頂點(diǎn)表
	EdgeType Edge[MaxVerterNum][MaxVerterNum];		// 鄰接矩陣
	int vexNum, arcNum;								// 圖當(dāng)前頂點(diǎn)數(shù)和弧數(shù)
}MGraph;

/*清除緩沖區(qū)的換行符*/
void Clean(void)
{
	while (getchar() != '\n')
		continue;
}

/* 建立無向網(wǎng)圖的鄰接矩陣表示 */
void CreateMGraph(MGraph* G);

/* 迪杰斯特拉（Dijkstra) 算法*/
typedef int Patharc[MaxVerterNum];			// 用于存儲(chǔ)最短路徑下標(biāo)的數(shù)組，從源點(diǎn)Vi到頂點(diǎn)Vj之間的最短路徑的前驅(qū)
typedef int ShortPathTable[MaxVerterNum];	// 用于存儲(chǔ)到各點(diǎn)最短路徑的權(quán)值和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc path, ShortPathTable D);

/* 輸出最短路徑 */
/* Dijkstra算法的結(jié)果輸出 */
void Show_ShortestPath_Dijkstra(Patharc path, ShortPathTable dist, MGraph G, int v0);

int main(void)
{
	MGraph G;
	Patharc path;
	ShortPathTable dist;
	CreateMGraph(&G);
	for (int i = 0; i < G.vexNum; i++) // 輸出各點(diǎn)到各點(diǎn)的最短路徑序列，不再局限于一個(gè)頂點(diǎn)
	{
		ShortestPath_Dijkstra(G, i, path, dist);
		Show_ShortestPath_Dijkstra(path, dist, G, i);
	}
	return 0;
}

/* 建立無向網(wǎng)圖的鄰接矩陣表示 */
void CreateMGraph(MGraph* G)
{
	int i, j, k, w;
	printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");
	scanf("%d %d", &G->vexNum, &G->arcNum);			// 獲取無向圖頂點(diǎn)數(shù)和邊數(shù)
	printf("請(qǐng)輸入全部頂點(diǎn)信息：\n");
	Clean();									    // 將換行符去除
	for (i = 0; i < G->vexNum; i++)					// 讀取頂點(diǎn)信息，建立頂點(diǎn)表
		scanf("%c", &G->Vexs[i]);
	for (i = 0; i < G->vexNum; i++)
		for (j = 0; j < G->vexNum; j++)
			G->Edge[i][j] = INFINITY;				// 鄰接矩陣初始化
	for (k = 0; k < G->arcNum; k++)					// 讀入arcNum條邊，建立鄰接矩陣
	{
		printf("請(qǐng)輸入邊（Vi, Vj)上的下標(biāo)i，下標(biāo)j和權(quán)w：\n");
		scanf("%d %d %d", &i, &j, &w);				// 獲取邊和權(quán)
		G->Edge[i][j] = w;							// 無向圖矩陣對(duì)稱
		G->Edge[j][i] = G->Edge[i][j];
	}
	return;
}

/* 迪杰斯特拉（Dijkstra) 算法*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc path, ShortPathTable dist)
{
	int v, w, k, min;
	int final[MaxVerterNum];				/* final[w] = 1表示求得頂點(diǎn) v0 至 vw的最短路                    徑，即已訪問過頂點(diǎn)vw*/
	for (v = 0; v < G.vexNum; v++)
	{
		final[v] = 0;						// 全部頂點(diǎn)初始化為未知最短路徑狀態(tài)
		dist[v] = G.Edge[v0][v];			// 將與v0點(diǎn)有連線的頂點(diǎn)加上權(quán)值
		path[v] = -1;						// 初始化路勁數(shù)組p為-1
	}
	dist[v0] = 0;							// v0至v0路徑為0
	final[v0] = 1;							// v0至v0不需要路徑
	/* 開始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑*/
	for (v = 1; v < G.vexNum; v++)
	{
		min = INFINITY;						// 當(dāng)前所知離v0頂點(diǎn)的最近距離
		for (w = 0; w < G.vexNum; w++)		// 尋找離v0最近的頂點(diǎn)
		{
			if (!final[w] && dist[w] < min)
			{
				k = w;
				min = dist[w];				// w頂點(diǎn)離v0頂點(diǎn)更近
			}
		}
		final[k] = 1;						// 將目前找到的最近的頂點(diǎn)置為1
		for (w = 0; w < G.vexNum; w++)		// 修正當(dāng)前最短路徑及距離
		{
			/* 如果經(jīng)過v頂點(diǎn)的路徑比現(xiàn)在這條路徑的長(zhǎng)度短的話 */
			if (!final[w] && (min + G.Edge[k][w] < dist[w]))
			{
				/* 找到了更短的路徑，修改D[w]和P[w] */
				dist[w] = min + G.Edge[k][w];	// 修改當(dāng)前路徑長(zhǎng)度
				path[w] = k;
			}
		}
	}
}

/* 輸出最短路徑 */
/* Dijkstra算法的結(jié)果輸出 */
void Show_ShortestPath_Dijkstra(Patharc path, ShortPathTable dist, MGraph G, int v)
{
	int w, k;
	printf("V%d到各點(diǎn)的最短路徑如下：\n", v);
	for (w = 0; w < G.vexNum; w++)
	{
		if (w != v)
		{
			printf("V%d-V%d weight: %d", v, w, dist[w]);
			k = path[w];
			printf(" path: V%d", w);
			while (k != -1)  // 當(dāng) k = -1 ，結(jié)束循環(huán)并輸出源點(diǎn)
			{
				printf(" <- V%d", k);
				k = path[k];
			}
			printf(" <- V%d\n", v);
		}
	}
	printf("\n");
}

（1） Dijkstra算法函數(shù)分析

/* 迪杰斯特拉（Dijkstra) 算法*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc path, ShortPathTable dist)
{
	int v, w, k, min;
	int final[MaxVerterNum];				// final[w] = 1表示求得頂點(diǎn) v0 至 vw的最短路徑，即已訪問過頂點(diǎn)vw
	for (v = 0; v < G.vexNum; v++)
	{
		final[v] = 0;						// 全部頂點(diǎn)初始化為未知最短路徑狀態(tài)
		dist[v] = G.Edge[v0][v];			// 將與v0點(diǎn)有連線的頂點(diǎn)加上權(quán)值
		path[v] = -1;						// 初始化路勁數(shù)組p為-1
	}
	dist[v0] = 0;							// v0至v0路徑為0
	final[v0] = 1;							// v0至v0不需要路徑
	/* 開始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑*/
	for (v = 1; v < G.vexNum; v++)
	{
		min = INFINITY;						// 當(dāng)前所知離v0頂點(diǎn)的最近距離
		for (w = 0; w < G.vexNum; w++)		// 尋找離v0最近的頂點(diǎn)
		{
			if (!final[w] && dist[w] < min)
			{
				k = w;
				min = dist[w];				// w頂點(diǎn)離v0頂點(diǎn)更近
			}
		}
		final[k] = 1;						// 將目前找到的最近的頂點(diǎn)置為1
		for (w = 0; w < G.vexNum; w++)		// 修正當(dāng)前最短路徑及距離
		{
			/* 如果經(jīng)過v頂點(diǎn)的路徑比現(xiàn)在這條路徑的長(zhǎng)度短的話 */
			if (!final[w] && (min + G.Edge[k][w] < dist[w]))
			{
				/* 找到了更短的路徑，修改D[w]和P[w] */
				dist[w] = min + G.Edge[k][w];	// 修改當(dāng)前路徑長(zhǎng)度
				path[w] = k;
			}
		}
	}
}

? ? ? ? ?上面數(shù)組final[]保存已有路徑的結(jié)點(diǎn)，有最短路徑的結(jié)點(diǎn)的值為 1，無最短路徑的結(jié)點(diǎn)的值為 0，path[]數(shù)組記錄結(jié)點(diǎn) V?的前驅(qū)結(jié)點(diǎn)，dist[]數(shù)組，記錄結(jié)點(diǎn) V?的前驅(qū)結(jié)點(diǎn)。

? ? ? ? 首先進(jìn)行初始化，final[]數(shù)組的元素的值均為 0，path[]數(shù)組的值均為 -1,當(dāng)path[i]=-1時(shí)，說明此結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即是源點(diǎn)V，dist[]的元素值初始化為源點(diǎn)V到鄰接點(diǎn)的距離。

? ? ? ? 接著進(jìn)入for循環(huán)，for循環(huán)內(nèi)的第一個(gè)for循環(huán)用于找到 dist[] 數(shù)組的最小值。

? ? ? ? for循環(huán)內(nèi)的第二個(gè)for循環(huán)用于進(jìn)行修正。

? ? ? ? 以上便是Dijkstra算法函數(shù)的基本內(nèi)容。三大塊——初始化，找dist[]最小元素、修正路徑。

人生是一場(chǎng)無休、無歇、無情的戰(zhàn)斗，凡是要做個(gè)夠得上稱為人的人，都得時(shí)時(shí)向無形的敵人作戰(zhàn)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——羅曼·羅蘭

以此句獻(xiàn)給看這篇博客的每一個(gè)人。文章來源地址http://www.zghlxwxcb.cn/news/detail-414335.html

到了這里，關(guān)于圖算法——求最短路徑（Dijkstra算法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！