最短路径算法问题

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

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

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