欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最短路——floyd算法

程序员文章站 2024-03-16 13:02:58
...

1. Floyd算法的介绍

  • 算法的特点:
    弗洛伊德算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。

  • Floyd-Warshall算法不能解决带有“负权回路”(或者叫“负权环”)的图,因为带有“负权回路”的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->…->1->2->3这样路径中,每绕一次1->-2>3这样的环,最短路就会减少1,永远找不到最短路。其实如果一个图中带有“负权回路”那么这个图则没有最短路。

  • 最短路——floyd算法

  • 算法的思路

通过Floyd计算图G=(V,E)中各个顶点的最短路径时,需要引入两个矩阵,矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j],表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点(即i-->b[i][j]-->j)。

假设图G中顶点个数为N,则需要对矩阵D和矩阵P进行N次更新。初始时,矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值;如果i和j不相邻,则a[i][j]=∞,矩阵P的值为顶点b[i][j]的j的值。 接下来开始,对矩阵D进行N次更新。第1次更新时,如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”),则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理,第k次更新时,如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”,则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后,操作完成!

2. Floyd算法的实例过程

上面,我们已经介绍了算法的思路,如果,你觉得还是不理解,那么通过一个实际的例子,把算法的过程过一遍,你就明白了,如下图,我们求下图的每个点对之间的最短路径的过程如下:

最短路——floyd算法

第一步,我们先初始化两个矩阵,得到下图两个矩阵:
最短路——floyd算法

最短路——floyd算法

第二步,以v1为中阶,更新两个矩阵:
发现,a[1][0]+a[0][6] < a[1][6] 和a[6][0]+a[0][1] < a[6][1],所以我们只需要矩阵D和矩阵P,结果如下:

最短路——floyd算法

最短路——floyd算法

通过矩阵P,我发现v2–v7的最短路径是:v2–v1–v7

第三步:以v2作为中介,来更新我们的两个矩阵,使用同样的原理,扫描整个矩阵,得到如下图的结果:

最短路——floyd算法
最短路——floyd算法

OK,到这里我们也就应该明白Floyd算法是如何工作的了,他每次都会选择一个中介点,然后,遍历整个矩阵,查找需要更新的值,下面还剩下五步,就不继续演示下去了,理解了方法,我们就可以写代码了。

floyd算法裸题:https://vjudge.net/contest/239724#status/20172202939/B/0/

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int maze[110][110];
int main()
{
   int i,j,n;
   while(~scanf("%d",&n)&&n)
   {
      for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
          maze[i][j]=(i==j?0:inf);
      for(i=1;i<=n;i++)
      {
         int a,b,m;
         scanf("%d",&m);
         for(j=0;j<m;j++){
             scanf("%d%d",&a,&b);
             maze[i][a]=b;
          }
      }

      //floyd 拿一个点去更新所有两点之间的最短距离,直至所有的点都用完
      for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
          for(int k=1;k<=n;k++)
            maze[j][k]=min(maze[j][k],maze[j][i]+maze[i][k]);
      int t,u,ans,minn=inf;
      for(i=1;i<=n;i++)
      {
         ans=0;
         for(j=1;j<=n;j++)
            if(maze[i][j]>ans)
               ans=max(ans,maze[i][j]);
         if(minn>ans)
         {
            minn=ans;
            u=i;
         }
      }
      if(minn==inf)
         printf("disjoint\n");
      else
         printf("%d %d\n",u,minn);
   }
   return 0;
}