2021-06-22 邻接矩阵，Dijkstra算法输出最短路径

本文主要是介绍2021-06-22 邻接矩阵，Dijkstra算法输出最短路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这里是图

全部代码

#include<stdio.h> 
int main()
{
	int inf = 999999;//表示两个点之间未相连 
	int e[20][20];邻接矩阵存储边
	int dis[20];//储存起点到其余点的最短路径
	int book[20];//表示点是否被遍历
	int n, u, min; //n总点数，u标记点，min最短边
	int count1 = 1,count2 = 1;
	char node[] = {"0ABCDEFGHIJKLMN"};
	char start1,last1;//初位置点 
	printf("请输入初末位置点：\n");
	scanf("%c %c",&start1,&last1);
	int start2,last2;//初末位置点序号,一共点 
	for(int i = 1;node[i]!='\0';i++)
	{
		if(node[i]==start1)
			start2 = i;
		if(node[i]==last1)
			last2 = i;
		n = i;//总点数 
	}
	printf("起始位置=%c，终点位置=%c。",node[start2],node[last2]);
//	scanf("%d %d", &n, &m);///n表示顶点个数，m表示边的条数
	///初始化
	for (int i = 1; i <= n; i++)///这里创建的是一个邻接矩阵，n*n的矩阵
		for (int j = 1; j <= n; j++)
			if (i == j) 
			e[i][j] = 0;
			else 
			e[i][j] = inf;
		
	//手动提前将图存入 
    e[1][2]=1,e[1][3]=1,e[1][4]=3;
    e[2][7]=2;
    e[3][5]=1;
    e[4][13]=3;
    e[5][6]=1;
    e[6][9]=2;
    e[7][10]=5;
    e[9][12]=3;
    e[10][12]=2;
	e[11][12]=2,e[11][14]=6;
	e[13][14]=5;
	//变成无向图 
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			if(e[i][j] != inf)
			e[j][i] = e[i][j];
		}
	}
	//测试输入的图是否正确 
//	for(int i = 1;i<=n;i++)
//	{
//		for(int j = 1;j<=n;j++)
//		{
//		    if( e[i][j]!=inf )
//		    printf("e[%d][%d] = %d\t",i,j,e[i][j]);
//		}
//	}
	 
	//初始化dis数组,这里要求的是起始顶点到其余各点的初始路程
	for (int i = 1; i <= n; i++)
	{
		dis[i] = e[start2][i];
	}
	//初始化book数组,这里面存的是已经被标记过的点
	for (int i = 1; i <= n; i++)
	{
		book[i] = 0;
	}
		
	book[start2] = 1;///表示该点是已经被标记过的点
// 	path1[count1++]=start2;
// 	path2[count2++]=start2;
	//核心代码
	for (int i = 1; i <= n - 1; i++)
	{
		min = inf;
		for (int j = 1; j <= n; j++)///找到相邻点中未标记点中的最小值
			{
				if (book[j] == 0 && dis[j]<min)
				{
					min = dis[j];
					u = j;
				}
			}
			book[u] = 1;
		
			for (int k = 1; k <= n; k++)///找到相邻的结点
			{
				if (e[u][k]<inf)
				{
					if (dis[k]>dis[u] + e[u][k])  //判断距离，核心思想 
						{
							dis[k] = dis[u] + e[u][k];
						}
				}
			}
	}
			///输出最终结果
		for(int i = 1;i<n;i++)
		{
//			printf("%c->",node[path[i]]);
			
		}

		printf("\n点%c到点%c最短距离=%d ",node[start2],node[last2], dis[last2]);
		return 0;
}

这篇关于2021-06-22 邻接矩阵，Dijkstra算法输出最短路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！