最短路径

Hoyoak 2019-08-11 20:35:00
原文地址:https://www.cnblogs.com/Hoyoak/p/11336583.html

没有用的话qaq :
Ummmm…图论的大部分知识本来早就有学过,只是一直没有写成博文来梳理,但既然上了qbxt DP图论就写一篇来总结下,主要是来听DP的,但…由于太菜的原因,DP听得天花乱坠QWQ


图中的最短路算法分为单源最短路算法(dijkstra,Bellman-food,spfa)和多源最短路算法(floyd),单源最短路算法是求图上一点到其他任意一点的最短路径,多源最短路算法是求图上任意两点之间的最短路。
一,多源最短路算法
Floyd弗洛伊德算法,运用了动态规划的思想,用邻接矩阵存储,期初将从任何一点到其他所有点的最短路都置成正无穷,然后输入时修改有的权值,其主要思想是动态规划,在最外围枚举点,看看有没有一个点可以更新两点之间的最短路。

代码简单易懂

memset(dis,0x3f,sizeof(dis));
for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

时间复杂度为O(n^3 ),空间复杂度为O(n^2),时间和空间均不是很优,一般较少采用,一般在求n范围较小的多源最短路题中才有出现。
可以适用于有负权边的情况,可以判断图的连通性,可以传递闭包


二,单源最短路算法
1,Dijkstra
a.将所有点分为两个集合,最短路确定的集合S 和最短路未确定的集合T,初始S ={s}
b.求T 中每个点v 的当前最短路dv = min<u,v>∈E,u∈S{du + wu,v}
c.取出T 中dv 最小的点,其最短路一定就是dv,将其加入S
d.不断重复上面的操作,直到所有点的最短路都确定

与普利姆的思想基本相同,代码实现也基本相同,同样朴素写法时间复杂度较劣,可以采用堆优化至O((N + M)logN)

inline void dijsktra(int s)
{
    for(int i=1;i<=n;i++)
        dist[i]=INF,vis[i]=false;
    heap.push(make_pair(0,s));
    vis[s]=true;
    while(!heap.empty())
    {
        int p=heap.top().second; 
        heap.pop();
        if(vis[p]) continue;
        vis[p]=true;
        for(int i=first[p];i;i=edge[i].nxt)
        {
            int e=edge[i].ed,d=edge[i].len;
            if(dist[e]>dist[p]+d)
            {
                dist[e]=dist[p]+d;
                heap.push(make_pair(-dist[e],e));
            }
        }
    }
}

Dijikstra算法是图论最短路算法中最高效的算法,但注意其不适用于含有负权边的情况。


3,Bellmanfood,SPFA

**其实是一个东西啦,SPFA是对Bellfood的优化,所以在这里就只整理SPFA了,比起Dijkstra,SPFA的用途更为广泛,其适用于有负权边的情况,可以判断一个图里是否有负环,但硬伤是效率,极容易被卡。
我们先看Bellmanfood的算法流程:
a.初始令ds = 0,其余di =∞

b. 依次使用每一条边< u, v > 更新,dv min{dv , du + wu,v}
c.不断循环直到所有di 都不会更新
d.因为任何一条最短路包含至多n − 1 条边,没有负环则不超过n 轮就会停止
SPFA考虑使用队列优化Bellman-Ford 算法,如果更新了du,则将u入队。每次取队首u 更新其邻点v 的dv。因为Bellmanfood会遍历一些不可能完成松弛操作的情况。**

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

struct node
{
    int ed,len,nxt;
};
node edge[2333];
int n,m,first[2333],dis[2333],cnt;
bool vis[2333];

queue <int> q;

inline void add_edge(int s,int e,int d)
{
    cnt++;
    edge[cnt].ed=e;
    edge[cnt].len=d;
    edge[cnt].nxt=first[s];
    first[s]=cnt;
}

inline void spfa(int st)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(dis));
    q.push(st); vis[st]=true;
    while(!q.empty())
    {
        int p=q.front(); vis[p]=false;
        for(int i=first[p];i;i=edge[i].nxt)
        {
            int e=edge[i].ed;
            int d=edge[i].len;
            int newd=dis[p]+d;
            if(newd<dis[e])
            {
                dis[e]=newd;
                if(!vis[e])
                {
                    q.push(e);
                    vis[e]=true;
                }
            }
        }
    }
    return;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int s,e,d;
        scanf("%d%d%d",&s,&e,&d);
        add_edge(s,e,d);
        add_edge(e,s,d);
    }
    spfa(1);
    return 0;
}//随手一写,不保证编译能过 Orz QwQ

SPFA判负环,就要有一个点的进队次数大于等于N,那么我们就认为有负环,因为负环会产生最短路为无限小,因此它会在那不停的转,有时候对于比较稠密的图,可能会卡SPFA判负环,所以对于比较稠密的图把队列换成栈可以更快的找出负环。

队列实现代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

struct node
{
    int ed,len,nxt;
};
node edge[2333];
int n,m,first[2333],inq[2333],dis[2333],cnt;
bool vis[2333];

queue <int> q;

inline void add_edge(int s,int e,int d)
{
    cnt++;
    edge[cnt].ed=e;
    edge[cnt].len=d;
    edge[cnt].nxt=first[s];
    first[s]=cnt;
}

inline bool spfa(int st)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(dis));
    q.push(st); vis[st]=true; inq[st]++;
    while(!q.empty())
    {
        int p=q.front(); vis[p]=false;
        for(int i=first[p];i;i=edge[i].nxt)
        {
            int e=edge[i].ed;
            int d=edge[i].len;
            int newd=dis[p]+d;
            if(newd<dis[e])
            {
                dis[e]=newd;
                if(!vis[e])
                {
                    q.push(e);
                    inq[e]++;
                    vis[e]=true;
                    if(inq[e]>=n) return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int s,e,d;
        scanf("%d%d%d",&s,&e,&d);
        add_edge(s,e,d);
        add_edge(e,s,d);
    }
    spfa(1);
    return 0;
}

写在最后,Yousiki Orz Orz

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。