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

思想

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; 
 }