本文共 2943 字，大约阅读时间需要 9 分钟。

本质就是贪心算法。

特点：对于每次循环确定的vk，v0与vk的距离是不断增加的。

#include
   
    using namespace std;#define MAXVEX 9#define INFINITY 65536typedef struct {   	int arc[MAXVEX][MAXVEX];//邻接矩阵	int numVEXS;//顶点个数}MGraph;void ShortestPath_Dijkstra(MGraph&G);int main() {   	MGraph G;	G.numVEXS = 9;	for (int i = 0; i < G.numVEXS; i++)		for (int j = 0; j < G.numVEXS; j++)		{   			if (i < j)				G.arc[i][j] = INFINITY;			if (i == j)				G.arc[i][i] = 0;		}	G.arc[0][1] = 1; G.arc[0][2] = 5;	G.arc[1][2] = 3; G.arc[1][3] = 7; G.arc[1][4] = 5;	G.arc[2][4] = 1; G.arc[2][5] = 7;	G.arc[3][4] = 2; G.arc[3][6] = 3;	G.arc[4][5] = 3; G.arc[4][6] = 6; G.arc[4][7] = 9;	G.arc[5][7] = 5;	G.arc[6][7] = 2; G.arc[6][8] = 7;	G.arc[7][8] = 4;	for (int i = 0; i < G.numVEXS; i++)		for (int j = 0; j < G.numVEXS; j++)		{   			if (i < j)				G.arc[j][i] = G.arc[i][j];		}	ShortestPath_Dijkstra(G);	system("pause");	return 0;}void ShortestPath_Dijkstra(MGraph&G) {   	int k, min;	int D[MAXVEX] = {    0 }, P[MAXVEX] = {    0 }, flag[MAXVEX] = {    0 };//D[v]表示v0到v的最短路径长度和,final[v]=1表示v0到v的最短路径已经被求出,P数组用来最终确定路径用	for (int i = 0; i < G.numVEXS; i++)		D[i] = G.arc[0][i];	flag[0] = 1;//v0到v0不需要求最短路径	//start	for (int n = 1; n < G.numVEXS; n++) {   //开始大循环（次数为G.numVEXS-1）		min = INFINITY;		for (int i = 0; i < G.numVEXS; i++)		{   			if (!flag[i] && D[i] < min)			{   				min = D[i];//找出当前离v0最近的且未被确定的顶点vk				k = i;//记录下标			}		}		flag[k] = 1;//把顶点vk置为1		//在已经找到v0与vk的最短路径的基础上，对和vk直接相连的且未被确定的顶点进行计算，得到v0与它们的当前距离		for (int i = 0; i < G.numVEXS; i++)		{   			if (!flag[i] && min + G.arc[k][i] < D[i]) //如果找到了更短的路径，则修正D和P			{   				D[i] = min + G.arc[k][i];				P[i] = k;//表示vk是vi的前驱			}		}	}	//打印路径	while (P[k] != k) {   		cout << P[k] << "-->" << k << endl;		k = P[k];	}}
   

若要求v5到各个顶点的最短路径，只需要修改代码如下：

void ShortestPath_Dijkstra(MGraph&G) {   	int k, min;	int D[MAXVEX] = {    0 }, P[MAXVEX] = {    5,5,5,5,5,5,5,5,5 }, flag[MAXVEX] = {    0 };//D[v]表示v0到v的最短路径长度和,final[v]=1表示v0到v的最短路径已经被求出,P数组用来最终确定路径用	for (int i = 0; i < G.numVEXS; i++)		D[i] = G.arc[5][i];	flag[5] = 1;//v5到v5不需要求最短路径	//start	for (int n = 1; n < G.numVEXS; n++) {   //开始大循环（次数为G.numVEXS-1）		min = INFINITY;		for (int i = 0; i < G.numVEXS; i++)		{   			if (!flag[i] && D[i] < min)			{   				min = D[i];//找出当前离v5最近的且未被确定的顶点vk				k = i;//记录下标			}		}		flag[k] = 1;//把顶点vk置为1				//在已经找到v5与vk的最短路径的基础上，对和vk直接相连的且未被确定的顶点进行计算，得到v5与它们的当前距离		for (int i = 0; i < G.numVEXS; i++)		{   			if (!flag[i] && min + G.arc[k][i] < D[i]) //如果找到了更短的路径，则修正D和P			{   				D[i] = min + G.arc[k][i];				P[i] = k;//表示vk是vi的前驱			}		}	}	//打印路径	while (P[k] != k) {   		cout << P[k] << "-->" << k << endl;		k = P[k];	}}