最短路径四大算法「建议收藏」

最短路径四大算法「建议收藏」熟悉的最短路算法就几种:bellman-ford,dijkstra,spfa,floyd。首先说明一点,就是关于负环的问题。bellman-ford可以用于边权为负的图中,图里有负环也可以,如果有负环,算法会检测出负环。时间复杂度O(VE);dijkstra只能用于边权都为正的图中。时间复杂度O(n2);spfa是个bellman-ford的优化算法,本质是bellman-for

大家好,又见面了,我是你们的朋友全栈君。

熟悉的最短路算法就几种: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作为弧尾的出边表。
这里写图片描述
用数组实现
这里写图片描述
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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136217.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Java实现 Hello World

    Java实现 Hello WorldHelloWorld记事本手写HelloWorldeclipse编辑器从零到一实现HelloWorld记事本手写HelloWorld1.新建Hello文本文件输入以下代码eclipse编辑器从零到一实现HelloWorld

  • adminLTE的介绍

    adminLTE的介绍一.adminLTE的介绍adminLTE的官方网站:adminLTE官方网站和github:adminLTE的github演示地址:adminLTE演示地址adminLTE是基于bootstrap3的前端框架,并且将bootstrap3进行修改来适应自身的样式。adminLTE除了可以使用bootstrap3的大多数样式之外,自身也提供了一些非常实用的样式包装,并且在样式演

  • MyEclipse SVN插件的安装及使用

    MyEclipse SVN插件的安装及使用MyEclipseSVN插件安装有两种,在线安装和手动安装一、(一)、在线安装1.打开Myeclipse,在菜单栏中选择Help→SoftwareUpdates→FindandInstall;2.选择Searchfornewfeaturesto

  • MySQL删除数据库[通俗易懂]

    MySQL删除数据库[通俗易懂]MySQL删除数据库

  • nginx实现负载均衡几种方式_nginx如何负载均衡

    nginx实现负载均衡几种方式_nginx如何负载均衡Nginx负载均衡配置实例详解(转)负载均衡是我们大流量网站要做的一个东西,下面我来给大家介绍在Nginx服务器上进行负载均衡配置方法,希望对有需要的同学有所帮助哦。负载均衡先来简单了解一下什么是负载均衡,单从字面上的意思来理解就可以解释N台服务器平均分担负载,不会因为某台服务器负载高宕机而某台服务器闲置的情况。那么负载均衡的前提就是要有多台服务器才能实现,也就是两台以上即可。测试环境由于没有服务器,所以本次测试直接host指定域名,然后在VMware里安装了三台CentOS。测试域名

  • 《架构之美》笔记_印象笔记如何创建目录

    《架构之美》笔记_印象笔记如何创建目录美是创造矛盾并解决矛盾。架构的多关注点(例如业务逻辑、系统扩展性、持久、并发)和简洁性就是一种矛盾,美丽的架构能解决这种矛盾,使人内心产生愉悦;随着关注点的增加,架构也在不断演进;术:分层、组件化、服务化、标准化、缓存、分离、队列、复制、冗余、代理;道:如何恰到好处地使用术,例如顿悟变化的道理、博弈中寻找平衡、相对与绝对的奥秘、开放的心态;爱因斯坦说:『让它尽可能简单,但不要过于简单』,美

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号