图的Dijkstra算法——C/C++

Myth丶恋晨 2021-12-22 21:23 197阅读 0赞

例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

## 一、算法原理 ##

1.首先，引入一个辅助向量 dist\[\]，它的每个分量 dist\[\] 表示当前所找到的，从起始点（即源点）到其它每个顶点的长度。  
例如，dist\[6\] = 16表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中 dist\[\] 的值是在不断逼近最终结果但在过程中不一定就等于长度。

2.dist\[\] 的初始状态为0：若从 v 到 vj 有边，则 dist\[\] 为边上的权值，否则置dist\[\]为∞。  
显然，长度为 dist\[j\] = Min\{ dist\[\] | vi∈V \} 的路径就是从 v 出发到顶点 vj 的长度最短的一条路径，路径为（v,vj）。

3.那么，下一条长度次短的是哪一条呢？也就是找到从源点到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点到顶点的最短路径长度。  
假设该次短路径的终点是 vk，则可想而知，这条路径要么是(v,vk)，或者是(v,vj,vk)。它的长度就是最小的路径长度。

4.一般情况下，假设S为已求得的从源点出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为 x）要么是(v,x)，或者是从源点出发的中间只经过S中的顶点而最后到达顶点的路径。因此，下一条长度次短的的最短路径长度必是 dist\[\]= Min\{ dist\[\]| vi ∈V-S \}，其中 dist\[\] 要么是(v,vi)上的权值，或者弧(v,vk,vi)上的权值之和。

## 二、算法思想 ##

1、 初始时令 S=\{V0\},U=V-S=\{其余顶点\}，T中顶点对应的距离值  
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值  
若不存在<V0,Vi>，d(V0,Vi)为∞  
2.、从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中  
3.、对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值  
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

## 三、算法实现 ##

**1、Dijkstra算法**

void Dijkstra(MatGraph LG, int v) {
    	int dist[MAXV];									//存储权值
    	int path[MAXV];									//是否有路径
    	int S[MAXV];									//S[i]==0表示顶点 i 在S中, S[i]==1 表示 顶点 i 在 U 中
    	int MinDis;										//最小的权值
    	int u = 0;										//记录最短路径的顶点
    	int i, j;
    	for (i = 0; i < LG.n; i++) {
    		dist[i] = LG.adjMat[v][i];					//距离初始化
    		S[i] = 0;									//S[] 初始化
    		if (LG.adjMat[v][i] < 32767) {				//路径初始化
    			path[i] = v;							//顶点 v 到顶点 i 有边时，置顶点 i 的前一个顶点为 v
    		}
    		else {
    			path[i] = -1;							//顶点 v 到顶点 i 无边时，置顶点 i 的前一个顶点为 -1
    		}
    	}
    	S[v] = 1;										//源点编号 v 放入 S
    	path[v] = 0;									
    	for (i = 0; i < LG.n - 1; i++) {				//循环求 v 到所有顶点的最短路径
    		MinDis = INF;								//置最大长度初值
    		for (j = 0; j < LG.n; j++) {
    			if (S[j] == 0 && dist[j] < MinDis) {	//选取不在 S 中（即 U 中）且就有路径长度的顶点 u
    				u = j;
    				MinDis = dist[j];					//得到顶点、路径长度
    			}
    		}
    		S[u] = 1;									//顶点 u 加入 S
    		for (j = 0; j < LG.n; j++) {				//修改最短路径
    			if (S[j] == 0) {
    				if (LG.adjMat[u][j] < INF && dist[u] + LG.adjMat[u][j] < dist[j]) {
    					dist[j] = dist[u] + LG.adjMat[u][j];
    					path[j] = u;
    				}
    			}
    		}
    	}
    	displayPath(LG, dist, path, S, v);				//输出最短路径
    }

**2、输出单源最短路径**

void displayPath(MatGraph LG, int dist[], int path[], int S[], int v) {
    	int i, j, k;
    	int aPath[MAXV];								//存放一条最短路径（逆向）
    	int d;											//顶点个数
    	for (i = 0; i < LG.n; i++) {					//循环输出从顶点 v 到 i 的路径
    		if (S[i] == 1 && i != v) {
    			printf("从顶点 %d 到顶点 %d 的路径长度为：%d\t 路径为:", v, i, dist[i]);
    			d = 0;
    			aPath[d] = i;							//添加路径上的终点
    			k = path[i];
    			if (k == -1) {							//没有路径
    				printf("无路径\n");
    			}
    			else {									//存在路径就输出
    				while (k != v) {
    					d++;
    					aPath[d] = k;
    					k = path[k];
    				}
    				d++;
    				aPath[d] = v;						//添加路径上的起点
    				printf("%d ", aPath[d]);			//输出起点
    				for (j = d - 1; j >= 0; j--) {		//输出其他顶点
    					printf("%d ", aPath[j]);
    				}
    				printf("\n");
    			}
    		}
    	}
    }

## 四、整体框架 ##

#include<stdio.h>
    #include<malloc.h>
    
    #define MAXV 7					//最大顶点个数 
    #define INF 32767				//定义 ∞
    //∞ == 32767 ,int 型的最大范围（2位）= 2^(2*8-1)，TC告诉我们int占用2个字节，而VC和LGCC告诉我们int占用4个字节
    //图：Graph
    //顶点：Vertex
    //邻接：Adjacency
    //矩阵：Matrix
    //表：List
    //边：Edge 
    
    typedef struct vertex {
    	int number;					//顶点的编号 	
    }VertexType; 					//别名，顶点的类型 
    
    typedef struct matrix {
    	int n;						//顶点个数
    	int e;						//边数 
    	int adjMat[MAXV][MAXV];		//邻接矩阵数组			
    	VertexType ver[MAXV];		//存放顶点信息 
    }MatGraph;						//别名，完整的图邻接矩阵类型
    
    typedef struct eNode {
    	int adjVer;					//该边的邻接点编号 
    	int weiLGht;				//该边的的信息，如权值 
    	struct eNode* nextEdLGe;	//指向下一条边的指针 
    }EdgeNode; 						//别名，边结点的类型 
    
    typedef struct vNode {
    	EdgeNode* firstEdLGe;		//指向第一个边结点 
    }VNode; 						//别名，邻接表的头结点类型 
    
    typedef struct list {
    	int n;						//顶点个数
    	int e;						//边数
    	VNode adjList[MAXV];		//邻接表的头结点数组 
    }ListGraph;						//别名，完整的图邻接表类型 
    
    //创建图的邻接表 
    void createAdjListGraph(ListGraph* &LG, int A[MAXV][MAXV], int n, int e) {
    	int i, j;
    	EdgeNode* p;
    	LG = (ListGraph*)malloc(sizeof(ListGraph));
    	for (i = 0; i < n; i++) {
    		LG->adjList[i].firstEdLGe = NULL;						//给邻接表中所有头结点指针域置初值 
    	}
    	for (i = 0; i < n; i++) {									//检查邻接矩阵中的每个元素 
    		for (j = n - 1; j >= 0; j--) {
    			if (A[i][j] != 0) {									//存在一条边 
    				p = (EdgeNode*)malloc(sizeof(EdgeNode));		//申请一个结点内存
    				p->adjVer = j;									//存放邻接点 
    				p->weiLGht = A[i][j];							//存放权值
    				p->nextEdLGe = NULL;
    
    				p->nextEdLGe = LG->adjList[i].firstEdLGe;		//头插法 
    				LG->adjList[i].firstEdLGe = p;
    			}
    		}
    	}
    	LG->n = n;
    	LG->e = e;
    }
    
    //输出邻接表 
    void displayAdjList(ListGraph* LG) {
    	int i;
    	EdgeNode* p;
    	for (i = 0; i < MAXV; i++) {
    		p = LG->adjList[i].firstEdLGe;
    		printf("%d:", i);
    		while (p != NULL) {
    			if (p->weiLGht != 32767) {
    				printf("%2d[%d]->", p->adjVer, p->weiLGht);
    			}
    			p = p->nextEdLGe;
    		}
    		printf(" NULL\n");
    	}
    }
    
    //输出邻接矩阵
    void displayAdjMat(MatGraph LG) {
    	int i, j;
    	for (i = 0; i < MAXV; i++) {
    		for (j = 0; j < MAXV; j++) {
    			if (LG.adjMat[i][j] == 0) {
    				printf("%4s", "0");
    			}
    			else if (LG.adjMat[i][j] == 32767) {
    				printf("%4s", "∞");
    			}
    			else {
    				printf("%4d", LG.adjMat[i][j]);
    			}
    		}
    		printf("\n");
    	}
    }
    
    //邻接表转换为邻接矩阵
    void ListToMat(ListGraph* LG, MatGraph& MG) {
    	int i, j;
    	EdgeNode* p;
    	for (i = 0; i < MAXV; i++) {
    		for (j = 0; j < MAXV; j++) {
    			MG.adjMat[i][j] = 0;
    		}
    	}
    	for (i = 0; i < LG->n; i++) {
    		p = LG->adjList[i].firstEdLGe;
    		while (p != NULL) {
    			MG.adjMat[i][p->adjVer] = p->weiLGht;
    			p = p->nextEdLGe;
    		}
    	}
    	MG.n = LG->n;
    	MG.e = LG->e;
    }
    
    //输出单源最短路径
    void displayPath(MatGraph LG, int dist[], int path[], int S[], int v) {
    	int i, j, k;
    	int aPath[MAXV];								//存放一条最短路径（逆向）
    	int d;											//顶点个数
    	for (i = 0; i < LG.n; i++) {					//循环输出从顶点 v 到 i 的路径
    		if (S[i] == 1 && i != v) {
    			printf("从顶点 %d 到顶点 %d 的路径长度为：%d\t 路径为:", v, i, dist[i]);
    			d = 0;
    			aPath[d] = i;							//添加路径上的终点
    			k = path[i];
    			if (k == -1) {							//没有路径
    				printf("无路径\n");
    			}
    			else {									//存在路径就输出
    				while (k != v) {
    					d++;
    					aPath[d] = k;
    					k = path[k];
    				}
    				d++;
    				aPath[d] = v;						//添加路径上的起点
    				printf("%d ", aPath[d]);			//输出起点
    				for (j = d - 1; j >= 0; j--) {		//输出其他顶点
    					printf("%d ", aPath[j]);
    				}
    				printf("\n");
    			}
    		}
    	}
    }
    
    //Dijkstra算法
    void Dijkstra(MatGraph LG, int v) {
    	int dist[MAXV];									//存储权值
    	int path[MAXV];									//是否有路径
    	int S[MAXV];									//S[i]==0表示顶点 i 在S中, S[i]==1 表示 顶点 i 在 U 中
    	int MinDis;										//最小的权值
    	int u = 0;										//记录最短路径的顶点
    	int i, j;
    	for (i = 0; i < LG.n; i++) {
    		dist[i] = LG.adjMat[v][i];					//距离初始化
    		S[i] = 0;									//S[] 初始化
    		if (LG.adjMat[v][i] < 32767) {				//路径初始化
    			path[i] = v;							//顶点 v 到顶点 i 有边时，置顶点 i 的前一个顶点为 v
    		}
    		else {
    			path[i] = -1;							//顶点 v 到顶点 i 无边时，置顶点 i 的前一个顶点为 -1
    		}
    	}
    	S[v] = 1;										//源点编号 v 放入 S
    	path[v] = 0;									
    	for (i = 0; i < LG.n - 1; i++) {				//循环求 v 到所有顶点的最短路径
    		MinDis = INF;								//置最大长度初值
    		for (j = 0; j < LG.n; j++) {
    			if (S[j] == 0 && dist[j] < MinDis) {	//选取不在 S 中（即 U 中）且就有路径长度的顶点 u
    				u = j;
    				MinDis = dist[j];					//得到顶点、路径长度
    			}
    		}
    		S[u] = 1;									//顶点 u 加入 S
    		for (j = 0; j < LG.n; j++) {				//修改最短路径
    			if (S[j] == 0) {
    				if (LG.adjMat[u][j] < INF && dist[u] + LG.adjMat[u][j] < dist[j]) {
    					dist[j] = dist[u] + LG.adjMat[u][j];
    					path[j] = u;
    				}
    			}
    		}
    	}
    	displayPath(LG, dist, path, S, v);				//输出最短路径
    }
    
    int main() {
    	ListGraph* LG;
    	MatGraph MG;
    	int array[MAXV][MAXV] = {
    		{  0,  4,  6,  6,INF,INF,INF},
    		{INF,  0,  1,INF,  7,INF,INF},
    		{INF,INF,  0,INF,  6,  4,INF},
    		{INF,INF,  2,  0,INF,  5,INF},
    		{INF,INF,INF,INF,  0,INF,  6},
    		{INF,INF,INF,INF,  1,  0,  8},
    		{INF,INF,INF,INF,INF,INF,  0}
    	};
    
    	int e = 12;
    	createAdjListGraph(LG, array, MAXV, e);
    	displayAdjList(LG);
    	printf("\n");
    
    	ListToMat(LG, MG);
    	displayAdjMat(MG);
    	printf("\n");
    
    	Dijkstra(MG, 0);
    	printf("\n");
    
    	return 0;
    }

## 五、结果展示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20211220/e90387b261c741008938182b0a8417f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211220/d9feeb4654104bf6877c949d0239145d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 2]: /images/20211220/f8aba98fe62f4938880932b5fc12e85d.png