最短路径—Floyd算法

Floyd算法

所有顶点对之间的最短路径问题是：对于给定的有向网络G=(V,E)，要对G中任意两个顶点v,w(v不等于w),找出v到w的最短路径。当然我们可以n次执行DIJKSTRA算法，用FLOYD则更为直接，两种方法的时间复杂度都是一样的。

1.定义概览

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N³)，空间复杂度为O(N²)。

2.算法描述

1)算法思想原理：

Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）

从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

2).算法描述：

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。　　

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

以下面的有向网络为例：

 #include<stdio.h>

 #define n 5   //结点数目

 #define maxsize 160  //表示两点间不可达

 int path[n][n];//路径矩阵

 void floyd(int A[][n],int C[][n]);  //A是路径长度矩阵，C是有向网络G的带权邻接矩阵

 void main()

 {

  printf("               ——所有顶点对之间的最短路径：Floyd算法——\n");

  printf("（160为无穷远，不可达）\n");

  int A[n][n],C[n][n]={

   {,,maxsize,,},

   {maxsize,,,maxsize,maxsize},

   {maxsize,maxsize,,maxsize,},

   {maxsize,maxsize,,,},

   {maxsize,maxsize,maxsize,maxsize,}

  };

  floyd(A,C);

 }

 void floyd(int A[][n],int C[][n])  //A是路径长度矩阵，C是有向网络G的带权邻接矩阵

 {

  int i,j,k,next;

  int max=;

  for(i=;i<n;i++)//设置A和path的初值

  {

   for(j=;j<n;j++)

   {

    if(C[i][j]!=max)

     path[i][j]=j;   //j是i的后继

    else

     path[i][j]=;

    A[i][j]=C[i][j];

   }

  }

  for(k=;k<n;k++)

  //做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径Pij上

  {

   for(i=;i<n;i++)

   {

    for(j=;j<n;j++)

    {

     if(A[i][j]>(A[i][k]+A[k][j]))

     {

      A[i][j]=A[i][k]+A[k][j];  //修改长度

      path[i][j]=path[i][k];    //修改路径

     }

    }

   }

  }

  for(i=;i<n;i++)//输出所有顶点对i,j之间的最短路径Pij的长度及路径

  {

   for(j=;j<n;j++)

   {

    if(i!=j)

    {

     printf("%d到%d的最短距离为",i+,j+);

     printf("%d\n",A[i][j]);   //输出Pij的长度

     next=path[i][j];        //next为起点i的后继顶点

     printf("输出路径：\n");

     if(next==)

      printf("%d到%d不可达\n",i+,j+);

     else//Pij存在

     {

      printf("%d",i+);

      while(next!=j)

      {

       printf("——>%d",next+);  //打印后继点

       next=path[next][j];        //继续找下一个后继点

      }

      printf("——>%d\n",j+);       //打印终点

     }

     printf("****************************************************\n");

    }

   }

  }

 }

 运行结果：

                ——所有顶点对之间的最短路径：Floyd算法——

 （160为无穷远，不可达）

 1到2的最短距离为10

 输出路径：

 ——>

 ****************************************************

 1到3的最短距离为50

 输出路径：

 ——>——>

 ****************************************************

 1到4的最短距离为30

 输出路径：

 ——>

 ****************************************************

 1到5的最短距离为60

 输出路径：

 ——>——>——>

 ****************************************************

 2到1的最短距离为160

 输出路径：

 2到1不可达

 ****************************************************

 2到3的最短距离为50

 输出路径：

 ——>

 ****************************************************

 2到4的最短距离为160

 输出路径：

 2到4不可达

 ****************************************************

 2到5的最短距离为60

 输出路径：

 ——>——>

 ****************************************************

 3到1的最短距离为160

 输出路径：

 3到1不可达

 ****************************************************

 3到2的最短距离为160

 输出路径：

 3到2不可达

 ****************************************************

 3到4的最短距离为160

 输出路径：

 3到4不可达

 ****************************************************

 3到5的最短距离为10

 输出路径：

 ——>

 ****************************************************

 4到1的最短距离为160

 输出路径：

 4到1不可达

 ****************************************************

 4到2的最短距离为160

 输出路径：

 4到2不可达

 ****************************************************

 4到3的最短距离为20

 输出路径：

 ——>

 ****************************************************

 4到5的最短距离为30

 输出路径：

 ——>——>

 ****************************************************

 5到1的最短距离为160

 输出路径：

 5到1不可达

 ****************************************************

 5到2的最短距离为160

 输出路径：

 5到2不可达

 ****************************************************

 5到3的最短距离为160

 输出路径：

 5到3不可达

 ****************************************************

 5到4的最短距离为160

 输出路径：

 5到4不可达

 ****************************************************

参考：http://blog.sina.com.cn/s/blog_686d0fb001012r05.html

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

巴特西

最短路径—Floyd算法

最新文章

热门文章