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