单源最短路径Dijkstra算法

最新推荐文章于 2024-08-15 22:29:41 发布

slowwalker12

最新推荐文章于 2024-08-15 22:29:41 发布

阅读量160

点赞数

分类专栏：算法练习

本文链接：https://blog.csdn.net/oslowwalker/article/details/89043291

版权

算法练习专栏收录该内容

4 篇文章

订阅专栏

本文介绍了一种使用迪杰斯特拉算法寻找图中两点间最短路径的方法，并通过具体的邻接矩阵输入实例展示了算法的具体实现过程。文章详细解释了算法步骤，包括初始化阶段、寻找最短路径以及路径回溯等。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

# include<iostream>

using namespace std;

#define inf 10000

int a[5][5]={0,10,inf,30,100,
			 inf,0,50,inf,inf,
			 inf,inf,0,inf,10,
			 inf,inf,20,0,60,
			 inf,inf,inf,inf,0};          //邻接矩阵输入 

void dijkstra(int a[5][5],int n,int dis[],int pre[])
{
	int flag[n];
	flag[0]=1;
	for(int i=1;i<n;i++)
	{
		dis[i]=a[0][i];
		flag[i]=0;
		pre[i]=0;
	}            //dis[i]表示从初始节到i节点的最短路径长度，flag[i]=1表示i节点访问过，pre[i]为路径中节点i的上一个节点 
	for(int i=0;i<n;i++)
	{
		int min=inf;
		int u;
		for(int j=0;j<n;j++)
			if(dis[j]<min && !flag[j])
				{min=dis[j];u=j;}   //找dis最小边长且该边指向的节点未访问过 
			flag[u]=1;
		for(int j=0;j<n;j++)
		{
			if(!flag[j] && a[u][j]<inf)          //节点u和j之间有通路 
			{
				if(a[u][j]+dis[u]<dis[j])     // 若初始节点经过节点u到达j的长度小于直接到达j的长度 
				{
					dis[j]=a[u][j]+dis[u];    // 更新dis 
					pre[j]=u;       //记录上一个节点（以便将来输出具体路径） 
				}
			}
		}
		/*for(int i=1;i<5;i++){cout<<dis[i]<<"  ";
		}cout<<endl;*/
	}
}

int main()
{
	int dis[5],pre[5],way[5];
	dijkstra(a,5,dis,pre);
	findway(4,5,way,pre);
	cout<<"distance:"<<endl;
	for(int i=1;i<5;i++)
		cout<<dis[i]<<"  ";
	cout<<endl;
}