图论4-floyd

路漫 2020-03-26

大家想一想,spfa是从bfs演化过来的,dijkstra是贪心思想,由此可见,这些“高级”的最短路算法都是有基础算法演化得来的。

而我今天要说的算法就是由基础的动态规划演化出来的最短路算法-floyd

还有用一到题来开启今天的内容:GF和猫咪的玩具

题意分析:有n个圆环,将两个圆环用力拉可以将这两个圆环之间的绳索拉直(当然是最短的路径,因为要把更长的路径拉直最短的路径

就会被扯断),如果有两条长度一样的路径,只会拉直其中一条,问抓住两个圆环用力拉最多能拉直多少绳索。抽象一下题意,就是有

一个图包括n个点和m个长度为1的连接点的边,问任意两点间的最短路径长度的最大值是多少。

思路解析:如果要做这道题,当然可以做n遍spfa或dijkstra,但是那样的话写起来会很费劲,所以,我要隆重推荐这个算任意两点间最

短路的神器:floyd!这个算法是从动态规划中演化出来的,所以就用dp四步走来讲一下这个最短路算法。

1.状态:dis[i][j]表示从i到j的最短路。

2.初值:dis[i][j]=INF,对于每条路A—>B,dis[A][B]=1;

3.转移:dis[i][j]=min(dis[i][j],dis[i][k],dis[k][j]){1<=i,j,k<=n};

4.答案:看是什么题了,比如这道题就是max(dis[i][j]){1<=i,j<=n}

最后看一下这种算法的时间复杂度:转移中枚举状态是n^2,而转移是所以整个的时间复杂度是O(n^3),能通过这道题。

用途:一般用于稠密图任意点间的最短路计算。

所以代码就是这样的吗?

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

看起来没什么问题,但是一做发现答案完全不对啊,可是这不是完全按照四步走写出来的代码吗?的确是这样,但我们还忽略了一个问题,

那就是dp的先后顺序。必须要把前面的求完才能用前面的转移后面的,也就是说我们的dis[i][j]的含义还有一些问题,那就是没有规定它的

中转点k,也就是说dis[i][j]的真正含义是当枚举到k时,从i到j经历的中转点为1~k时i到j的最短路径长度。

所以真正的正确的floyd代码是这样的,如果还有不明白的看注释

int dis[NR][NR]; //dis[i][j]表示从考虑中转点到k(其中k是在循环里面的)时i到j的最短路径 
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]);//状态转移方程
//转移方程成立的原因:如果从i绕到k之后再绕到j比直接i到j更短,当然要选择短的那一种

最后,上这道题的完整代码:

#include<bits/stdc++.h>
using namespace std;
const int NR=1e2+10;
const int INF=0x3f3f3f3f;
int n,m;
int dis[NR][NR]; //dis[i][j]表示从考虑中转点到k(其中k是在循环里面的)时i到j的最短路径 
int read()//这道题不能用快读read否则有东西读不进去 
{
    int x=0,f=1;char ch=getchar();
    while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch<=‘9‘&&ch>=‘0‘){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    memset(dis,0x3f,sizeof(dis));//dis初值 
    scanf("%d%d",&n,&m);//点数和边数 
    for(int i=1;i<=n;i++) dis[i][i]=0;//从自己到自己当然长度为0 
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);//读入x到y有边, 
        dis[x][y]=dis[y][x]=1;//从x到y和从y到x都有长度为1的边 
    }
    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]);//状态转移方程
    //转移方程成立的原因:如果从i绕到k之后再绕到j比直接i到j更短,当然要选择短的那一种 
    int ans=0;
    for(int i=1;i<=n;i++)//统计答案时枚举起点 
        for(int j=i+1;j<=n;j++)//统计答案时枚举终点 
            if(dis[i][j]!=INF) ans=max(ans,dis[i][j]);//更新答案 
    printf("%d",ans);//输出答案 
    return 0;
}

相关推荐