最短路径算法问题

2021/4/8 12:12:56

本文主要是介绍最短路径算法问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.dijkstra算法(迪克斯特拉算法)/单源点算法

dijkstra算法,先找到距离源点最近的点,然后进行缓冲操作,所谓缓冲操作即将此点作为缓冲点,判断经过它是否可以缩短其他点到原点的距离,如果可以,更新距离。最后将这个点屏蔽(不再遍历这个点)。这样将所有的点遍历一遍就可以找到所有点到原点的最短距离。

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
int mp[1005][1005];
int vis[1005],dis[1005];
int n,m;//n个点,m条边
void Init ()
{
memset(mp,Inf,sizeof(mp));
for(int i=1;i<=n;i++)
{
mp[i][i]=0;//自己到自己的距离为零
}
}
void Getmap()
{
int u,v,w;
for(int t=1;t<=m;t++)
{
scanf("%d%d%d",&u,&v,&w);
if(mp[u][v]>w)
{
mp[u][v]=w;//看情况给边赋值
mp[v][u]=w;
}
}

}
void Dijkstra(int u)
{
memset(vis,0,sizeof(vis));//为了屏蔽最短已经是最短距离的点
for(int t=1;t<=n;t++)
{
dis[t]=mp[u][t];//给每一个到源点的距离赋初值
}
vis[u]=1;//屏蔽操作
for(int t=1;t<n;t++)
{
int minn=Inf,temp;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&dis[i]<minn)//找最短距离的点
{
minn=dis[i];
temp=i;
}
}
vis[temp]=1;
for(int i=1;i<=n;i++)
{
if(mp[temp][i]+dis[temp]<dis[i])//以最短距离为中转点,看是否可以更新其他点到原点的最短距离。
{
dis[i]=mp[temp][i]+dis[temp];
}
}
}
}
int main()
{
scanf("%d%d",&m,&n);
Init();
Getmap();
Dijkstra(n);//n为源点,根据题目而定。
printf("%d\n",dis[1]);//1为目的点。
return 0;
}



这篇关于最短路径算法问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程