欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

dijkstra单源最短路径-贪心算法

程序员文章站 2024-03-17 08:47:58
...

思想

1.集合v是整个点集。集合s中最初只有源点,另一个集合用v-s表示。
2.在集合v-s中找到最小的受限路径,将对应的点添加到集合s中。(受限路径:比如集合s中有点A B,集合v-s中有点D E。A->B->D A->B->E都叫受限路径,A->D->E就不是受限路径,因为除了最后一个点,其余点没有全部在集合s中。)
3.由于新加入了一个点,所以要更新还在集合v-s中的点对应的受限路径值。

代码中一些变量含义说明

dist[i]记录源点到点i的最短受限路径(i是集合v-s中的点)
prev[x]=u在x的最短路径中,u是x的前驱(我自己给出的代码中,最后没有输出路线,所以你们可以把和prev有关的代码注释掉)
c[i][j]记录权值

代码

#include <iostream>
using namespace std;
#define maxint 100000
int n;//顶点个数 
int dist[100];//dist[u]表示:源到点u的最短受限路径(u是集合v-s的点) 
int c[100][100];//记录边权
int prev[100];//记录前缀节点 
void dijkstra(int v)
{
	bool s[n+1];//true表示该点加入集合s,否则在集合v-s中
	/*数据初始化*/
	for(int i=1;i<=n;++i)
	{
		dist[i]=c[v][i];//初始时,s集合中只有源,受限路径=源到点i距离
		s[i]=false;//初始,所有点都在v-s中
		if(dist[i]==maxint) prev[i]=0;
		else prev[i]=v; 
	}
	s[v]=true;//初始s中只有源点
	dist[v]=0;	 
	for(int i=1;i<=n;++i)
	{	
		int u;int tmp=maxint;//两个存储中间值的变量 
		/*在集合v-s寻找dist最小的点*/ 
		for(int j=1;j<=n;++j)
			if(s[j]==false&&dist[j]<tmp)
			{
				u=j;tmp=dist[j];
			 } 
		s[u]=true;//将找到的点加入集合s 
		/*将u加入s后,更新dist*/
		for(int j=1;j<=n;++j)
			if(s[j]==false&&c[u][j]<maxint)
			{
				if(dist[j]>dist[u]+c[u][j])
				{	dist[j]=dist[u]+c[u][j];
					prev[j]=u;} 
			} 
	} 	
}
int main()
{
	

	cout<<"请输入顶点个数:";
	cin>>n;//顶点个数
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			c[i][j]=maxint;
	for(int i=1;i<=n;++i)
		dist[i]=maxint;
	cout<<"请输入边数:"; 
	int m;cin>>m; 
	cout<<"请输入边权,前两个参数是顶点编号,第三个参数为权值:"<<endl;
	int x,y,z;
	while(1) 
	{
		cin>>x>>y>>z;
		c[x][y]=z;//顶点x->y权值为z 
		--m;if(m==0) break;
	}
	cout<<"请输入源点编号:";
	int v;cin>>v;//源点
	dijkstra(v);
	cout<<endl;
	for(int i=1;i<=n;++i)
	 if(i!=v) cout<<v<<"到"<<i<<"的最短距离为"<<dist[i]<<endl; 
	return 0; 
 } 

dijkstra单源最短路径-贪心算法

相关标签: 算法设计