首先,何为最短路?

假设有五个点,每个点之间都有一条连线,并且赋予距离。给予一对起点与终点,让你求出从起点到终点的最短距离,或者最短时间。

 

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:还需要加油啊!