最短路径四大算法

今天药忘吃喽~ 2022-05-14 12:07 168阅读 0赞

熟悉的最短路算法就几种：bellman-ford，dijkstra，spfa，floyd。  
bellman-ford可以用于边权为负的图中，图里有负环也可以，如果有负环，算法会检测出负环。  
时间复杂度O（VE）;  
dijkstra只能用于边权都为正的图中。  
时间复杂度O（n2）；  
spfa是个bellman-ford的优化算法，本质是bellman-ford，所以适用性和bellman-ford一样。（用队列和邻接表优化）。  
时间复杂度O（KE）;  
floyd可以用于有负权的图中，即使有负环，算法也可以检测出来,可以求任意点的最短路径，有向图和无向图的最小环和最大环。  
时间复杂度O（n3）；  
任何题目中都要注意的有四点事项：图是有向图还是无向图、是否有负权边，是否有重边，顶点到自身的可达性。  
1、Dijkstra（单源点最短路）  
这个算法只能计算单元最短路，而且不能计算负权值，这个算法是贪心的思想， dis数组用来储存起始点到其他点的最短路，但开始时却是存的起始点到其他点的初始路程。通过n-1遍的遍历找最短。每次在剩余节点中找dist数组中的值最小的，加入到s数组中，并且把剩余节点的dist数组更新。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN = 0x3f3f3f3f;
    const int p = 1005;
    int a[p][p];//存放点与点的距离
    int dist[p];//源点到各个点的最短距离
    int pre[p];//计算过的点
    int s[p];//判断是否已经加入pre,是否已访问
    int n,m;
    void Dijkstra(int v)
    {
        int i,j;
        for(i = 0;i < n;++i)
        {
            if(i != v)
            {
                dist[i] = a[v][i];
            }
            s[i] = false;
        }
        s[v] = true;
        dist[v] = 0;
        pre[0]=v;
        //对各个数组进行初始化
        for(i = 0;i < n;++i)
        {
            int minset = MAXN;
            int u = v;
             for(j = 0; j < n;++j)
             {
                 if(!s[j] && dist[j] < minset)
                 //找到剩余节点中最小的节点
                 {
                     u = j;
                     minset = dist[u];
                 }
             }
             s[u] = true;
             //将节点标记为以访问，相当于加入s数组中
             for(j = 0;j < n;++j)
             {
                 if(!s[j] && a[u][j] < MAXN)
                 //a[u][j] < MAXN指更新u的可达点
                 {
                     if(dist[u] + a[u][j] < dist[j])
                     {
                         dist[j] = dist[u] + a[u][j];
                         pre[j] = u;
                         //储存得出最短路径的前一个节点，用于路径还原
                     }
                 }
             }
        }
    }
    int main()
    {
        int t;
        cin>>t;
        while(~scanf("%d %d",&n,&m))
        {
            memset(a,MAXN,sizeof(a));
            memset(dist,MAXN,sizeof(dist));
            int i,j;
            for(i = 0;i < m;++i)
            {
                int x,y,d;
                scanf("%d %d %d",&x,&y,&d);
                a[x-1][y-1]=d;
                a[y-1][x-1]=d;
            }
            //int v;
            //scanf("%d",&v);
            Dijkstra(0);
            for(int i = 0;i < n;++i)
            {
                printf("%d ",dist[i]);
            }
            printf("\n");
            /*for(int i = 0;i < n;++i)
            {
                printf("%d ",s[i]);
            }
            printf("\n");
            for(int i = 0;i < n;++i)
            {
                printf("%d ",pre[i]);
            }
            printf("\n");*/
        }
        return 0;
    }

Floyd:  
floyd算法是非常强大的，可以处理不少问题，复杂度是O（n^3）的，下面解析一下这个算法  
不少人可能刚接触floyd的时候非常容易把它写错，错误的写法就是三层循环的从外到内的变量分别为i，j，k，正确的写法应该是k，i，j。写错的原因是不理解floyd算法造成的，那么为什么从顺序是k，i，j呢？

其实floyd的算法本质是个动态规划！dp\[k\]\[i\]\[j\]代表i到j的中间节点（不包括i和j）都在区间\[1，k\]时，i到j的最短路。算法的最外层循环是个从小到大枚举k的过程，当最外层刚刚进入第k次循环的时候，我们已经得到了所有点对的dp\[k-1\]\[\]\[\]的值，也就是所有点对（i，j）的i到j的中间节点都在\[1，k-1\]区间的i到j的最短路。那么对任意的点对（i，j），如果他俩的最短路经过k点，则dp\[k\]\[i\]\[j\]=dp\[k-1\]\[i\]\[k\]+dp\[k-1\]\[k\]\[j\]；如果不经过k点，则dp\[k\]\[i\]\[j\]=dp\[k-1\]\[i\]\[j\]。所以当我们求dp\[k\]\[\]\[\]的时候，要保证所有的dp\[i-1\]\[\]\[\]都求出来了，因此，最外层循环是k。  
每一层都是有上一层决定，不会受这一层影响，所以可以利用滚动数组优化内存空间，将k去除掉

任意节点i到j的最短路径不外乎两种可能：1、直接从i到j；2、从i经过若干个节点k到j。Dis（i，j）表示节点i到j最短路径的距离，对于每一个节点k，检查Dis（i，k）+Dis（k，j）小于Dis(i,j),如果成立，Dis（i，j） = Dis（i，k）+Dis（k，j）；遍历每个k，每次更新的是除第k行和第k列的数。（十字交叉法，可百度）。

floyd能做很多事情，下面简单说两个，求有向图的最小环或者最大环（顶点数>=2），求无向图的最小环（顶点数>=3）。

先说求有向图最小环（最大环略）。有两种方法可以求，一种是设定g\[i\]\[i\]为无穷大，这样最后找所有的g\[i\]\[i\]里的最小值就行；另一种是正常做floyd，然后对每个点对（i，j），求g\[i\]\[j\]+dp\[n\]\[j\]\[i\]的最小值，这样的原理是最小环如果存在的话，那么可以枚举一个这个环里的边i->j，那么包含这条边的最小的环一定是i->j和dp\[n\]\[j\]\[i\]构成的最短路。

无向图的最小环做法和有向图不一样，是因为无向边可能会被用两次导致出错，举例说就是：枚举了一条边i->j，然后其与dp\[n\]\[j\]\[i\]的和作为一个结果，但是如果j到i的最短路就是边j->i的话，那么我们找的环其实只是一条边而已，这样的结果显然是错误的。正确的做法是先判断最小环再更新最短路。（为什么？）  
因为会出现重边的现象，所以一个环一定至少有三个点，所以每次先判断最小环，因为k必须是未用过的，此时的dist\[i\]\[j\]是遍历了k-1次的最短路，用完判断了再去更新k对应的最短路。每次比较dist\[i\]\[j\]+  
g\[i\]\[k\]+g\[k\]\[j\]的最小值。k—>i————>j—->k;这样一直保证环是三个点。

hdu1599（用Floyd求无向图的最小环）

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN = 100005;
    const int p = 105;
    int dist[p][p];
    int mp[p][p];
    int main()
    {
        int n,m;
        while(~scanf("%d %d",&n,&m))
        {
            int i,j,k;
            for(i = 0;i < n;++i)
            {
                for(j = 0;j < n;++j)
                {
                    dist[i][j] = MAXN;
                    mp[i][j] = MAXN;
                }
            }
            for(i = 0;i < m;++i)
            {
                int a,b,c;
                scanf("%d %d %d",&a,&b,&c);
                if(c < mp[a-1][b-1])
                       dist[a-1][b-1]=dist[b-1][a-1]=mp[b-1][a-1]=mp[a-1][b-1]=c;
            }
            int ans = MAXN;
            for(k = 0;k < n;++k)
            {
                for(i = 0;i < n;++i)
                {
                    for(j = i+1;j < n;++j)
                    //这里用i+1，防止i，j是不同的两个点
                    {
                        if(ans > dist[i][j] + mp[i][k] + mp[k][j])
                        {
                            ans = dist[i][j] + mp[i][k] + mp[k][j];
                        }
                    }
                }
                for(i = 0;i < n;++i)
                {
                    for(j = 0;j < n;++j)
                    {
                        if(dist[i][j] > dist[i][k] + dist[k][j])
                        {
                            dist[i][j] = dist[i][k] + dist[k][j];
                        }
                    }
                }
            }
            if(ans == MAXN)
                printf("It's impossible.\n");
            else
                printf("%d\n",ans);
        }
        return 0;
    }

Floyd的模板：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN = 0x3f3f3f3f;
    const int p = 1005;
    int dist[p][p];
    int path[p][p];
    int mp[p][p];
    int n,m;
    int Floyd()
    {
        int i,j,k;
        for(i = 0;i < n;++i)
        {
            for(j = 0;j < n;++j)
            {
                dist[i][i]=0;
                mp[i][i]=0;
            }
        }
        int ans = MAXN;
        for(k = 0;k < n;++k){
        for(i = 0;i < n;++i)
        {
            for(j = 0;j < n;++j)
            {
                if(dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
        }
        return ans;
    }
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            int i,j;
            memset(path,-1,sizeof(path));
            memset(dist,MAXN,sizeof(dist));
            memset(mp,MAXN,sizeof(mp));
            scanf("%d %d",&n,&m);
            for(int i = 0;i < m;++i)
            {
                int x,y,d;
                scanf("%d %d %d",&x,&y,&d);
                dist[x][y]=d;
                dist[y][x]=d;
                mp[x][y]=d;
                mp[y][x]=d;
            }
            printf("%d\n",Floyd());
            for(i = 0;i < n;++i)
            {
                for(j = 0;j < n;++j)
                {
                    printf("%d ",dist[i][j]);
                }
                cout<<endl;
            }
            for(i = 0;i < n;++i)
            {
                for(j = 0;j < n;++j)
                {
                    printf("%d ",path[i][j]);
                }
                cout<<endl;
            }
        }
        return 0;
    }

Bellman-Ford：  
适用范围：1、单源最短路径（从源点到其他所有点v）；  
2、有向图&无向图；  
3、边权可正可负  
4、差分约束系统  
图G(v,e),源点s，数组Distant\[i\]记录了从源点s到顶点i的路径长度，循环执行至多n-1次，n为顶点数。  
对每一条边e（u，v），如果Distant\[u\]+w\[u,v\]小于Distant\[v\],则Distant\[v\] = Distant\[u\]+w(u,v);  
每一次循环都会至少更新一个点，所以才会出现至多循环n-1次，一次更新是指用所有节点进行一次松弛操作，（为什么会出现循环一次都能至少确定一个节点的最短距离？）  
因为：1、将所有节点分为两类：已知最短距离的节点和剩余节点。  
2、这两类节点满足这样的性质：已知最短距离的节点的最短距离值都比剩余节点的最短路值小。  
3、易知到剩余节点的路径一定会经过已知节点。  
4、而从已知节点连到剩余节点的所以边中的最小的那个边，这条边所更新后的剩余节点就一定是确定的最短距离，从而多找到了一个能确定最短距离的节点（不用知道它是哪个节点）。

实现过程的三步：1、初始化所有的点，每一个点保存一个值，表示源点到这个点的距离其他点的值设为无穷大。  
2、进行循环，从1到n-1，进行松弛计算。  
3、遍历所有边，如果的d\[v\]大于d\[u\]+w(u,v)存在，则有从源点可达的权为负的回路。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int MAXN = 0x3f3f3f3f;
    const int p = 100005;
    typedef struct Graph{
       int u,v,cost;
    };
    //有向图
    Graph edge[p];//边表
    int pre[p];
    int dis[p];
    int n,m,v;//点数，边数，源点
    bool BellmanFloyd()
    {
        int i,j;
        for(i = 1;i <= n;++i)//最多进行n-1次更新
        {
            for(j = 0;j < m;++j)//每次遍历一下边表，至少找出一个点的最短路径
            {
                if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost)
                {
                    dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;
                }
            }
        }
        bool flag = true;
        for(i = 0;i < m;++i)//判断负环
        {
            if(dis[edge[i].v]>dis[edge[i].u]+edge[i].cost)
            {
                flag = false;
                break;
            }
        }
        return flag;
    }
    int main()
    {
        while(~scanf("%d %d",&n,&m))
        {
            int i,j;
            memset(dis,MAXN,sizeof(dis));
            memset(pre,-1,sizeof(pre));
            for(i = 0;i < m;++i)
            {
                scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].cost);
            }
            dis[1] = 0;
            pre[1] = 1;
            BellmanFloyd();
                for(i = 1;i <= n;++i)
                {
                    printf("%d ",dis[i]);
                }
                printf("\n");
        }
        return 0;
    }

介绍SPFA之前先介绍一个图的存储方式：邻接表（可以用来优化算法）  
可以用数组实现，因为本人不喜欢用指针实现，所以也没尝试。  
对于图来说，邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。  
邻接表的处理方法是这样的。  
1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。  
2、图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表。  
![这里写图片描述][20130429141605716]  
用数组实现  
![这里写图片描述][wKioL1NDrM-BEcO8AAA19M1T0qU426.jpg]  
next\[i\]存储的是“编号为i的边”的“前一条边”的编号。  
可通过next找到以某一个顶点为起始点的所有边。

SPFA是一种求单源最短路的算法（Bellman-ford的优化版）  
算法中需要用到的主要变量  
int n; //表示n个点，从1到n标号  
int s,t; //s为源点，t为终点  
int d\[N\]; //d\[i\]表示源点s到点i的最短路  
int p\[N\]; //记录路径（或者说记录前驱）  
queue q; //一个队列，用STL实现，当然可有手打队列，无所谓  
bool vis\[N\]; //vis\[i\]=1表示点i在队列中 vis\[i\]=0表示不在队列中  
几乎所有的最短路算法其步骤都可以分为两步  
1.初始化  
2.松弛操作  
初始化： d数组全部赋值为INF（无穷大）；p数组全部赋值为s（即源点），或者赋值为-1，表示还没有知道前驱点， 然后d\[s\]=0; 表示源点不用求最短路径，或者说最短路就是0。将源点入队；（另外记住在整个算法中有顶点入队了要记得标记vis数组，有顶点出队了记得消除那个标记）

队列+松弛操作  
读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令d\[v\]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队  
以此循环，直到队空为止就完成了单源最短路的求解

SPFA可以处理负权边  
定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。  
证明：  
每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d\[v\]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。（证毕）  
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。  
判断有无负环：  
如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）

算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int MAXN = 20005;
    const int MINX = 1005;
    int u[MAXN];
    int v[MAXN];
    int w[MAXN];
    int first[MINX];
    int ne[MAXN];
    int d[MINX];
    bool vis[MINX];
    int p[MINX];
    queue<int>que;
    void spfa_bfs()
    {
        int i,j;
        while(!que.empty())
        {
            int k = que.front();
            que.pop();
            vis[k] = 0;
            for(int x = first[k];x != -1;x = ne[x])
            {
                int y = v[x];
                if(d[y] > d[k] + w[x])
                {
                    d[y] = d[k] + w[x];
                    p[y] = x;
                    if(!vis[y]){
                        vis[y] = 1;
                        que.push(y);
                    }
                }
            }
        }
    }
    int main()
    {
        int n,m,s,t;
        while(~scanf("%d %d %d",&n,&m,&s))
        {
            int x,y,z;
            int i,j;
            memset(ne,-1,sizeof(ne));
            memset(first,-1,sizeof(first));
            memset(vis,0,sizeof(vis));
            memset(d,inf,sizeof(d));
            memset(p,-1,sizeof(p));
            d[s] = 0;
            vis[s] = 1;
            p[s] = s;
            que.push(s);
            for(i = 1;i <= m;++i)
            {
                scanf("%d %d %d",&x,&y,&z);
                u[i] = y;
                v[i] = x;
                w[i] = z;
                if(first[y] == -1){
                    first[y] = i;
                }
                else
                {
                    ne[i] = first[y];
                    first[y] = i;
                }
            }
            spfa_bfs();
            /*for(i = 1;i <= m;++i)
            {
                printf("%d %d %d %d %d\n",u[i],v[i],w[i],first[i],ne[i]);
            }
            for(i = 1;i <= n;++i)
            {
                printf("%d ",d[i]);
            }
            cout<<endl;*/
            scanf("%d",&t);
            int ptr;
            int mx = inf;
            for(j = 0;j < t;++j)
            {
                scanf("%d",&ptr);
                mx = (mx > d[ptr])?d[ptr]:mx;
            }
            if(mx == inf)
                printf("-1\n");
            else
                printf("%d\n",mx);
        }
        return 0;
    }

转自：[ qq\_36386435][qq_36386435]

[20130429141605716]: /images/20220514/0559b44c68b1441e8395a1eb20964787.png
[wKioL1NDrM-BEcO8AAA19M1T0qU426.jpg]: /images/20220514/a9d4505f24b9418cb1b3999e5ae8c5be.png
[qq_36386435]: https://blog.csdn.net/qq_36386435/article/details/77403223