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

三种最短路径算法：

floyd(O(n^3))、dijkstra(O(nlogn))、SPFA(O(KE))（k是进队列次数）

（1）floyd：效率较低

具体思路：将所有节点的距离都存在一个数组里，由于要枚举所有的两两组合以及每一个组合的“中转点”，再进行松弛操作

在求单源最短路径的时候就会浪费许多空间，但在求多源最短路时，复杂度仍是O(n^3)使用很广

#include<bits/stdc++.h>
const int INF = 2147483647;
const int maxn = 10005;
using namespace std;
int deal[1005][1005], n, m, s;
void floyd()
{
    for(int k = 1;k <= n;k++)
    {
        //这里要先枚举k（可以理解为中转点）
        for(int i = 1;i <= n;i++)
        {
            if(i == k || deal[i][k] == INF)
            {
                continue;    
            }
            for(int j = 1;j <= n;j++)
            {
                deal[i][j] = min(deal[i][j],deal[i][k]+deal[k][j]);\
                //松弛操作，即更新每两个点之间的距离
                //松弛操作有三角形的三边关系推出
                //即两边之和大于第三边    
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            deal[i][j] = INF;
        }
    }    //初始化，相当于memset(a,inf,sizeof(a))
    for(int i = 1, u, v, w;i <= m;i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        deal[u][v] = min(deal[u][v],w);//取min可以对付重边
    }
    floyd();
    deal[s][s] = 0;
    for(int i = 1;i <= n;i++)
    {
        printf("%d", deal[s][i]);    
    }
    return 0;
}

dijkstra：对于无负边的情况下可以达到O(nlogn)且很难被卡

具体思路：Dijkstra是基于一种贪心的策略，首先用数组dis记录起点到每个结点的最短路径，再用一个数组保存已经找到最短路径的点

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点记为已经找到最短路

此时完成一个顶点，再看这个点能否到达其它点（记为v），将dis[v]的值进行更新

不断重复上述动作，将所有的点都更新到最短路径

这种算法实际上是O(n^2)的时间复杂度，但我们发现在dis数组中选择最小值时，我们可以用一些数据结构来进行优化。线段树？平衡树？

其实我们可以用STL里的堆来进行优化，堆相对于线段树以及平衡树有着常数小，码量小等优点，并且堆的一个妙妙的性质就是可以在nlogn的时限内满足堆顶是堆内元素的最大（小）值，之不正是我们要的嘛？

以下是用堆优化dijkstra代码：
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
#define maxm 500005
#define INF  1234567890
inline int read()
{
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
struct Edge
{
    int u,v,w,next;
}e[maxm];
int head[maxn],cnt,n,m,s,vis[maxn],dis[maxn];
struct node
{
    int w,now;
    inline bool operator <(const node &x)const
    //重载运算符把最小的元素放在堆顶（大根堆）
    {
        return w>x.w;//这里注意符号要为'>'
    }
};
priority_queue<node>q;
//优先队列，其实这里一般使用一个pair，但为了方便理解所以用的结构体
inline void add(int u,int v,int w)
{
    e[++cnt].u=u;
    //这句话对于此题不需要，但在缩点之类的问题还是有用的
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    //存储该点的下一条边
    head[u]=cnt;
    //更新目前该点的最后一条边（就是这一条边）
}
//链式前向星加边
void dijkstra()
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=INF;
    }
    dis[s]=0;
    //赋初值
    q.push((node){0,s});
    while(!q.empty())
    //堆为空即为所有点都更新
    {
        node x=q.top();
        q.pop();
        int u=x.now;
        //记录堆顶（堆内最小的边）并将其弹出
        if(vis[u]) continue; 
        //没有遍历过才需要遍历
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        //搜索堆顶所有连边
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                //松弛操作
                q.push((node){dis[v],v});
                //把新遍历到的点加入堆中
            }
        }
    }
}
int main()
{
    n=read(),m=read(),s=read();
    for(int i=1,x,y,z;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        add(x,y,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    return 0;
}

SPFA：考场慎用，在毒瘤数据面前可能退化到O(nm)

具体思路：这里用的是STL队列，首先用数组dis记录起点到每个结点的最短路径，用邻接表来存储图，用vis数组记录当前节点是否在队列中

具体操作为：用队列来保存待优化的结点（类似于BFS），优化时每次取出队首结点，并且用队手节点来对最短路径进行更新并进行松弛操作

如果要对所连点的最短路径需要更新，且改点不在当前的队列中，就将改点加入队列

然后不断进行松弛操作，直至队列空为止。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
#define maxn 10005
#define maxm 500005
#define inf 1234567890
int n,m,s,tot,dis[maxn],head[maxn];
bool vis[maxn];
struct Edge
{
      int next,to,w;
}h[maxm];
void add(int u,int v,int w)
{
    h[++tot].next=head[u];
    h[tot].to=v;
    h[tot].w=w;
    head[u]=tot;
}
//上面和dijkstra算法基本上一样
queue<int> q;
//队列优化
inline void spfa()
{
    for(int i=1; i<=n; i++)
    {
        dis[i]=inf;
        //赋初值
    }
    int u,v;
    q.push(s);
    dis[s]=0;
    //将起点的值负为0
    vis[s]=1;//这句话可加可不加，因为循环的时候vis[s]又会被赋为0
    while(!q.empty())
    //当队列里没有元素的时候，那就已经更新了所有的单源最短路径
    {
        u=q.front();
        //将队手节点记录并弹出队首节点
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=h[i].next)
        //寻找与u相连的边
        {
            v=h[i].to;
            if(dis[v]>dis[u]+h[i].w)
            {
                dis[v]=dis[u]+h[i].w;
                //松弛操作，和floyd比较相似
                if(!vis[v])
                {
                //已经在队列里的点就不用再进入了
                      vis[v]=1;
                      q.push(v);
                }
            }
        }
    }
}
int main(){
    n=read(),m=read(),s=read();
    for(int i=1,u,v,w;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        add(u,v,w);
    }
    spfa();
    for(int i=1; i<=n; i++)
    {
        printf("%d ",dis[i]);
    }
    return 0;
}

 ps：资料参考https://www.cnblogs.com/mint-hexagram/p/14799308.html

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