图论最短路径算法（一）Floyed算法（弗洛伊德算法）

我会带着你远行 2021-09-22 23:34 539阅读 0赞

### 文章目录 ###

*   *  Floyed-Warshall算法 O(N^3)
     *   *  算法描述：
         *  算法分析&思想讲解：
         *  Floyed算法变形：
         *  应用场景
         *   *  【例1】最短路径问题
             *  【例2】牛的旅行

## Floyed-Warshall算法 O(N^3) ##

> 简称Floyed(弗洛伊德)算法，是最简单的最短路径算法，可以计算图中任意两点间的最短路径。Floyed的时间复杂度是O (N3)，适用于出现负边权的情况。

*以下没有特别说明的话，dis\[u\]\[v\]表示从u到v最短路径长度，w\[u\]\[v\]表示连接u，v的边的长度。*

### 算法描述： ###

初始化：点u、v如果有边相连，则dis\[u\]\[v\]=w\[u\]\[v\]。如果不相连则dis\[u\]\[v\]=0x7fffffff

For (k = 1; k <= n; k++)
        For (i = 1; i <= n; i++)
    	 For (j = 1; j <= n; j++)
    	     If (dis[i][j] >dis[i][k] + dis[k][j])
    	         dis[i][j] = dis[i][k] + dis[k][j];

算法结束：**dis\[i\]\[j\]得出的就是从i到j的最短路径。**

### 算法分析&思想讲解： ###

三层循环，第一层循环中间点k，第二第三层循环起点终点i、j，算法的思想很容易理解：如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离，那么就用这个更短的路径长度来更新原先点i到点j的距离。  
　　  
　　在上图中，因为dis\[1\]\[3\]+dis\[3\]\[2\]<dis\[1\]\[2\]，所以就用dis\[1\]\[3\]+dis\[3\]\[2\]来更新原先1到2的距离。  
　　  
　　我们在初始化时，把不相连的点之间的距离设为一个很大的数，不妨可以看作这两点相隔很远很远，如果两者之间有最短路径的话，就会更新成最短路径的长度。Floyed算法的时间复杂度是O(N3)。

### Floyed算法变形： ###

如果是一个没有边权的图，把相连的两点间的距离设为dis\[i\]\[j\]=true，不相连的两点设为dis\[i\]\[j\]=false，用Floyed算法的变形：

For (k = 1; k <= n; k++)
      For (i = 1; i <= n; i++)
        For (j = 1; j <= n; j++)
    　　  dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);

用这个办法可以判断一张图中的两点是否相连。

**最后再强调一点：用来循环中间点的变量k必须放在最外面一层循环。**

### 应用场景 ###

#### 【例1】最短路径问题 ####

**【问题描述】**  
　　平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。  
　　  
　　若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的  
　　  
　　任务是找出从一点到另一点之间的最短路径。  
　　  
**【输入格式】**  
　　[输入文件为short.in][short.in]，共n+m+3行，其中:  
　　  
　　第一行为整数n。  
　　  
　　第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。  
　　  
　　第n+2行为一个整数m，表示图中连线的个数。  
　　  
　　此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。  
　　  
　　最后一行：两个整数s和t，分别表示源点和目标点。  
　　  
**【输出格式】**  
　　输出文件为short.out，仅一行，一个实数（保留两位小数），表示从s到t的最短路径长度。

**【输入样例】**  
5  
0 0  
2 0  
2 2  
0 2  
3 1  
5  
1 2  
1 3  
1 4  
2 5  
3 5  
1 5

**【输出样例】**  
3.41

**【实例代码】**

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    using namespace std;
    int a[101][3];
    double f[101][101];
    int n,i,j,k,x,y,m,s,e;
    int main()
    { 
        cin >> n;
        for (i = 1; i <= n; i++)
            cin >> a[i][1] >> a[i][2];
        cin >> m;
        memset(f,0x7f,sizeof(f));                    //初始化f数组为最大值
        for (i = 1; i <= m; i++)                           //预处理出x、y间距离
        { 
          cin >> x >> y;
          f[y][x] = f[x][y] = sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
                         //pow(x,y)表示x^y，其中x,y必须为double类型，要用cmath库
        }
        cin >> s >> e;
        for (k = 1; k <= n; k++)                     //floyed 最短路算法
           for (i = 1; i <= n; i++)
              for (j = 1; j <= n; j++)
                 if ((i != j) && (i != k) && (j != k) && (f[i][k]+f[k][j] < f[i][j]))
                     f[i][j] = f[i][k] + f[k][j];
        printf("%.2lf\n",f[s][e]);
        return 0;
    }

#### 【例2】牛的旅行 ####

**【问题描述】**  
　　农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径 ( 注意，恰好一条 )。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离 ( 本题中所提到的所有距离指的都是最短的距离 )。考虑如下的两个牧场，图１是有5个牧区的牧场，牧区用“\*”表示，路径用直线表示。每一个牧区都有自己的坐标：  
　　![在这里插入图片描述][2019041017014928.png]  
　　图１所示的牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。 　　  
　　  
　　这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。  
　　  
　　注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。 　　  
　　  
　　现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。  
　　  
**【输入格式】**  
　 第 1 行：一个整数N (1 <= N <= 150), 表示牧区数； 　 第 2 到 N+1 行：每行两个整数X，Y ( 0 <= X，Y<= 100000 )， 表示N个牧区的坐标。每个牧区的坐标都是不一样的。 　 第 N+2 行到第 2N+1 行：每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵。 　  
　 例如，题目描述中的两个牧场的矩阵描述如下： 　　　　　　  
　 A B C D E F G H 　　　　　  
A 0 1 0 0 0 0 0 0 　　　　　  
B 1 0 1 1 1 0 0 0 　　　　　  
C 0 1 0 0 1 0 0 0 　　　　　  
D 0 1 0 0 1 0 0 0 　　　　　  
E 0 1 1 1 0 0 0 0 　　　　　  
F 0 0 0 0 0 0 1 0 　　　　　  
G 0 0 0 0 0 1 0 1 　　　　　  
H 0 0 0 0 0 0 1 0

输入数据中至少包括两个不连通的牧区。

**【输出格式】**  
　 只有一行，包括一个实数，表示所求答案。数字保留六位小数。

**【输入样例】**  
　 8  
　 10 10  
　 15 10  
　 20 10  
　 15 15  
　 20 15  
　 30 15  
　 25 10  
　 30 10  
　 01000000  
　 10111000  
　 01001000  
　 01001000  
　 01110000  
　 00000010  
　 00000101  
　 00000010  
　  
**【输出样例】**  
　 22.071068  
　  
**【算法分析】**  
　 用Floyed求出任两点间的最短路，然后求出每个点到所有可达的点的最大距离，记做mdis\[i\]。（Floyed算法）  
　 **r1=max(mdis\[i\])**  
　 然后枚举不连通的两点i,j，把他们连通，则新的直径是mdis\[i\]+mdis\[j\]+(i,j)间的距离。  
　 **r2=min(mdis\[i\]+mdis\[j\]+dis\[i,j\])  
　 re=max(r1,r2)**  
　 re就是所求。  
　  
**【参考程序】**

#include<iostream>
    #include<cmath>
    #include<cstring> 
    using namespace std;
    double f[151][151],m[151],minx,r,temp,x[151],y[151],maxint=1e12;
    double dist(int i,int j)
    { 
      return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])) ;  
    }
    int main()
    {  int i,j,n,k;char c;
      cin>>n;
      for(i=1;i<=n;i++)cin>>x[i]>>y[i];
      for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
        {  cin>>c;
          if(c=='1')f[i][j]=dist(i,j);
               else f[i][j]=maxint;
        }
      for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
            if(i!=j&&i!=k&&j!=k)
               if(f[i][k]<maxint-1&&f[k][j]<maxint-1)
                  if(f[i][j]>f[i][k]+f[k][j])
                    f[i][j]=f[i][k]+f[k][j];
       memset(m,0,sizeof(m));
       for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
         if(f[i][j]<maxint-1&&m[i]<f[i][j])m[i]=f[i][j]; 
       minx=1e20;
      for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
        if(i!=j&&f[i][j]>maxint-1)
         { temp=dist(i,j);
          if(minx>m[i]+m[j]+temp)minx=m[i]+m[j]+temp;
         }
      r=0;
      for(i=1;i<=n;i++)if (m[i]>minx)minx=m[i];
      printf("%.6lf",minx);
      return 0;
    }

[short.in]: http://xn--short-dq1hz7bn8jl38cn41f.in
[2019041017014928.png]: /images/20210920/cf042dddc579490397ce1e1839f76b98.png