图的最短路径--迪杰斯特拉算法 c语言

男娘i 2022-11-22 00:05 79阅读 0赞

还是按照书上的例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MaxInt 32767//无穷值设置 
    #define MVNum 100 //图的最大容量 ，也可以称为图的最大顶点数 
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1)//用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    
    typedef struct//图的结构体 
    { 
    	char vexs[MVNum];//顶点表 
    	int arcs[MVNum][MVNum];//邻接矩阵 
    	int vexnum,arcnum;//图的当前点数和边数 
    }AMGraph;
    
    void InitGraph(AMGraph &G)//图的初始化 
    { 
    	int i,j;
    	for(i = 0;i<MVNum;i++)
    		for(j = 0;j<MVNum;j++)
    			G.arcs[i][j] = MaxInt;//使邻接矩阵中的数据都初始化为0 
    }
    
    void CreateGraph(AMGraph &G)//图的创建 
    { 
    	int i;//记录次数 
    	char a;//顶点变量 
    	printf("请输入顶点数和边数:");
    	scanf("%d %d",&G.vexnum,&G.arcnum);
    	Interrupt();//该函数用于检测并吸收换行符 
    	printf("请输入顶点名称（连续输入）：");
    	for(i=0;i<G.vexnum;i++)
    	{ 
    		scanf("%c",&a);
    		G.vexs[i] = a;//第i个顶点的命名 
    	}
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k;//w为权值变量，j和k是用来记录次数的 
    	for(i=0;i<G.arcnum;i++)
    	{ 
    		printf("请输入边的两个顶点和权值w:");
    		scanf("%c %c %d",&b,&c,&w);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		for(j=0;j<G.vexnum;j++)
    		{ 
    			if(G.vexs[j] == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<G.vexnum;k++)
    		{ 
    			if(G.vexs[k] == c)//找到输入的顶点c的位置 
    			break;
    		}
    		G.arcs[j][k] = w;//权值赋值 
    	}
    }
    
    void InputGraph(AMGraph G)//邻接矩阵的输出 
    { 
    	int i,j;//记录次数 
    	printf("邻接矩阵为：\n ");
    	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++)//遍历邻接矩阵 
    			printf("%d ",G.arcs[i][j]);
    		printf("\n");
    	}
    }
    
    void ShortestPath_DIJ(AMGraph G,int v0)//用Dijkstra算法求有向图G的v0到其余顶点的最短路径 
    { 
    	int i,n,v,min,w;//下面所用到的所有变量 
    	n = G.vexnum;//顶点个数 
    	bool S[n];//辅助数组S[]的定义 
    	int D[n],Path[n];//辅助数组D[]和Path[]的定义 
    	for(v=0;v<n;v++)//辅助数组的初始化 
    	{ 
    		S[v] = false;
    		D[v] = G.arcs[v0][v];
    		if(D[v]<MaxInt)
    			Path[v] = v0;
    		else
    			Path[v] = -1;
    	}
    	S[v0] = true;
    	D[v0] = 0;//初始化结束 
    	for(i=1;i<n;i++)//对其余n-1个顶点，依次进行计算 
    	{ 
    		min = MaxInt;//暂定最小权值 
    		for(w=0;w<n;w++)
    			if(!S[w] && D[w]<min)
    			{ 
    				v = w;
    				min = D[w];//选择一条从v0出发的最短路径，终点为v 
    			}
    		S[v] = true;//用于记录已选择过 
    		for(w=0;w<n;w++)//更新从v0出发到集合V-S上所有顶点的最短路径长度 
    			if(!S[w] && (D[v]+G.arcs[v][w]<D[w]))
    			{ 
    				D[w] = D[v]+G.arcs[v][w];//更新D[w] 
    				Path[w] = v;//更新w的前驱为v 
    			}
    	}
    	//打印辅助数组最后结果 
    	for(i=0;i<n;i++)//打印D[] 
    		printf("D[%d]=%d ",i,D[i]);
    	printf("\n");
    	for(i=0;i<n;i++)//打印Path 
    		printf("Path[%d]=%d ",i,Path[i]);
    	printf("\n");
    }
    
    int main()
    { 
    	AMGraph G;
    	InitGraph(G);//图的初始化 
    	CreateGraph(G);//创建邻接矩阵 
    	InputGraph(G);//输出邻接矩阵
    	ShortestPath_DIJ(G,0);//Dijkstra算法，数字0可换成变量，这里是测试 
    	return 0;
    }

结果演示：  
辅助数组的初始化结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]  
代码运行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 2]  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/ebd7ba6e5dfa47b0bcea78e95ccb66da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201102223209251.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020110222324756.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0,size_16,color_FFFFFF,t_70#pic_center