首先，何为最短路？
假设有五个点，每个点之间都有一条连线，并且赋予距离。给予一对起点与终点，让你求出从起点到终点的最短距离，或者最短时间。
HDU2544.
这个问题可以枚举，从1-2，1-3,1-2-3等等并求出其最短的路线，但是如果数据太多怎么办。假如有1000个点，挨个枚举可能会枚举半年，所以这个时候引出几种算法，我们先来看第一种。以下算法我们都以一道题为例题：输入N，M（分别表示终点N，并且有M条边），接下来输入M行x，y，z分别表示从点x到点y的距离为z，求出1-N的最短距离，例如
2 3
1 2 4
1 3 1
2 3 1 输出结果应该是：2 即最短路线为 1-3-2；(如果未特殊情况说明，路线为双向）
一、Dijkstra算法
1.首先，盗图。（如有侵权，立即删除）
2.我们从起点出发，依次遍历与起点相连的每一个点，更新他们与起点的距离，比如该图中，与6的距离会变成14，与3的距离变成9，与2的距离变成7.然后再选择一个与起点距离最短的点，再去更新与之相邻的点，这样由于每次都选择的是最优解（即最短路）所以，每个点都遍历完之后，每个点上面的数值，就是与起点的最短距离。（还不懂就认真看盗的动图）。
3.所以首先加边，然后进行算法，第一个代码有加边环节，剩下的就不写了，只写算法，下面我们看一下求解这道题的Dijkstra算法：
时间复杂度O（n^2) 空间复杂度O(n)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
typedef long long ll;
using namespace std;
const int maxn=1e6+5;
const int INF=1e9;
struct node{
int e;//记录可以到达地址
int w;//到达e的距离或者时间
int next;//储存下一个地址
}edge[maxn];
int head[maxn];//头指针数组
ll cnt=0;//记录指针后移
int dis[maxn];
int vis[maxn];
void addedge(int u,int v,int w)
{
edge[cnt].e=v;//u->v;
edge[cnt].w=w;
edge[cnt].next=head[u];//把这一组数据放到u后面；
head[u]=cnt++;
/*或者还有一种写***出警告，但不报错
edge[cnt]={v,w,head[u]};
head[u]=cnt++;*/
}
void restart()
{
memset(head,-1,sizeof(head));
cnt=0;//多组输入中这个而一定要加；
}
void Dijkstra(int n)
{
//这个地方一定要注意点的范围，如果包括0，i需要从0开始。
for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=0;//对dis数组进行赋予最大值，方便更新。
dis[1]=0; //起点赋予0，从起点开始；标记过就确定最小距离，不在更新标记为1.
while(1)
{
int k=-1;int len=INF;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&len>dis[i])
{
len=dis[i];
k=i;//擂台法比较出当前与起点距离最小的点。
}
}
if(k==-1) break;//找不到点，全部遍历完，结束。
vis[k]=1;
for(int i=head[k];i!=-1;i=edge[i].next)//该处使用的链式前向星访问，如有不懂，阅读上一篇文章
{
int u=edge[i].e;
if(!vis[u]&&dis[u]>len+edge[i].w)
dis[u]=len+edge[i].w;
}
}
}
int main()
{
ll m,n;
while(scanf("%lld%lld",&m,&n)&&m&&n)
{
restart();//一定不要忘记初始化！
ll maxx=0;
for(int i=1;i<=n;i++)
{
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
ll a=max(u,v);
maxx=max(maxx,a);//记录最大能到达的点，以便于可以全部遍历。
}
/* for(int i=head[1];i!=-1;i=edge[i].next)
printf("1->%d need %d\n",edge[i].e,edge[i].w);///检测一下边是否加对*/
Dijkstra(maxx);
printf("%d\n",dis[m]);
}
return 0;
}
二、Floyd算法
1.首先，再次盗图：
2.我们从图中可以看出如果从1-到4.有3种可能，1-4或者1-3-4或者1-2-3-4.我们基于动态规划的思想，一个点经过点k或者不经过点k距离变不变小。所以这里的状态转移方程应该是 dp[i][j]=dp[i][k]+dp[k][j](经过点k变短）否则dp[i][j]=dp[i][j]。
Floyd算法，时间复杂度O（n^3） 空间复杂度O（n^2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
typedef long long ll;
using namespace std;
const int maxn=1e3+5;
const int INF=1e9;
int dp[maxn][maxn];
void addedge(int u,int v, int w)
{
dp[u][v]=w;
dp[v][u]=w;
}
void restart()
{
for(int i=0;i<maxn;i++)
for(int j=0;j<maxn;j++)
dp[i][j]=INF;//初始化一定要赋值为最大，不然没法更新刚开始的每一条路最短距离。
}
void Floyd(int n)
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dp[i][j]>dp[i][k]+dp[k][j])
dp[i][j]=dp[i][k]+dp[k][j];
}
int main()
{
ll m,n;
while(scanf("%lld%lld",&m,&n)&&m&&n)
{
restart();
ll maxx=-1;
for(int i=1;i<=n;i++)
{
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
addedge(u,v,w);//这个函数里已经确定是无向了不需要再加反向边。
ll a=max(u,v);
maxx=max(maxx,a);
}
Floyd(maxx);
printf("%d\n",dp[1][m]);
}
return 0;
}
三、队列求短路【Spfa】
1. 该算法运用C++里的STL库，queue进行逐步更新。
2.首先，还是盗图。
3.运用队列的性质，从起点开始，将与他相连的点遍历，判断这个点是否在队列当中，如果不在队列当中就把这个点加上，在队列中则不能加，只更新他最小距离。
Spfa算法
时间复杂度：O（nlgn）-O（n^2）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
typedef long long ll;
using namespace std;
const int maxn=1e6+5;
const int INF=1e9;
struct node{
int e;//记录可以到达地址
int w;//到达e的距离或者时间
int next;//储存下一个地址
}edge[maxn];
int head[maxn];//头指针数组
ll cnt=0;//记录指针后移
int dis[maxn];
bool inq[maxn];
void addedge(int u,int v,int w)
{
edge[cnt].e=v;//u->v;
edge[cnt].w=w;
edge[cnt].next=head[u];//把这一组数据放到u后面；
head[u]=cnt++;
/*或者还有一种写***出警告，但不报错
edge[cnt]={v,w,head[u]};
head[u]=cnt++;*/
}
void restart()
{
for(int i=0;i<maxn;i++)
{
dis[i]=INF;inq[i]=true;
head[i]=-1;
}
cnt=0;
}
void Spfa()
{
queue<int>q;//创建队列
q.push(1);
dis[1]=0;//以S为起点的话应该q.push(S)
while(!q.empty())//只要队列不空
{
int u=q.front();//用u记录
q.pop();//扔掉第一个元素
inq[u]=true;//不在队列当中标记为0
for(int i=head[u];i!=-1;i=edge[i].next)
{
int y=edge[i].e;
if(dis[y]>dis[u]+edge[i].w)
{
dis[y]=dis[u]+edge[i].w;
if(inq[y]==true)//如果不在队列中
{
q.push(y);
inq[y]=false;//标记为在队列中
}
}
}
}
}
int main()
{
ll m,n;
while(scanf("%lld%lld",&m,&n)&&m&&n)
{
restart();
ll maxx=0;
for(int i=1;i<=n;i++)
{
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
Spfa();
printf("%d\n",dis[m]);
}
return 0;
}
四、堆优化队列【priority queue】
根据Dijkstra的思想，每次应该从距离起点最近的点去更新其他点，所以用堆优化求最短路。
时间复杂度 O(nlgn)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
typedef long long ll;
using namespace std;
const int maxn=1e6+5;
const int INF=1e9;
struct node{
int e;//记录可以到达地址
int w;//到达e的距离或者时间
int next;//储存下一个地址
}edge[maxn];
int head[maxn];//头指针数组
ll cnt=0;//记录指针后移
int dis[maxn];
struct PII{
int id;
int len;
};//创建一个结构体用来让优化队列有选择的排序。
bool operator<(PII a,PII b)
{
return a.len>b.len;//重载priority中的小于号，使其按照这个顺序排序。
}
void addedge(int u,int v,int w)
{
edge[cnt].e=v;//u->v;
edge[cnt].w=w;
edge[cnt].next=head[u];//把这一组数据放到u后面；
head[u]=cnt++;
/*或者还有一种写***出警告，但不报错
edge[cnt]={v,w,head[u]};
head[u]=cnt++;*/
}
void restart()
{
for(int i=0;i<maxn;i++)
{
dis[i]=INF;
head[i]=-1;
}
cnt=0;
}
void motiSpfa()
{
priority_queue<PII>q;
dis[1]=0;
q.push({1,dis[1]});
while(!q.empty())
{
PII x=q.top();//取第一个元素
q.pop();//扔掉第一个元素
if(dis[x.id]!=x.len) continue;//如果距离已经更新，说明又有新的点，放进去。
for(int i=head[x.id];i!=-1;i=edge[i].next)
{
int u=edge[i].e;
if(dis[u]>dis[x.id]+edge[i].w)
{
dis[u]=dis[x.id]+edge[i].w;
q.push({u,dis[u]});
}
}
}
}
int main()
{
ll m,n;
while(scanf("%lld%lld",&m,&n)&&m&&n)
{
restart();
ll maxx=0;
for(int i=1;i<=n;i++)
{
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
motiSpfa();
printf("%d\n",dis[m]);
}
return 0;
}
五、总结
以上就是全部的在我已知范围内的求最短路的方法，总结一下这些方法的根本都在于，去更新最小距离，Spfa是对Dijistra的优化，而priorityqueue是对queue的优化。Floyd是基于动态规划的思想每次都更新最短路，首先更新自己与其他点的距离，再去更新，经过点K的距离。
最后PS:还需要加油啊！
京公网安备 11010502036488号