来自百度百科

Floyd算法

弗洛伊德算法一般指Floyd算法
Floyd算法又称为插点法，是一种利用 动态规划的思想寻找给定的 加权图中多源点之间 最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年 图灵奖获得者、斯坦福大学计算机科学系教授 罗伯特·弗洛伊德命名。
<dl class="basicInfo&#45;block basicInfo&#45;left"> <dt class="basicInfo&#45;item name"> 中文名 </dt> <dd class="basicInfo&#45;item value"> 弗洛伊德算法 </dd> <dt class="basicInfo&#45;item name"> 外文名 </dt> <dd class="basicInfo&#45;item value"> Floyd(Floyd-Warshall) </dd> </dl> <dl class="basicInfo&#45;block basicInfo&#45;right"> <dt class="basicInfo&#45;item name"> 时间复杂度 </dt> <dd class="basicInfo&#45;item value"> O（n^3） </dd> <dt class="basicInfo&#45;item name"> 空间复杂度 </dt> <dd class="basicInfo&#45;item value"> O（n^2） </dd> <dt class="basicInfo&#45;item name"> 作    用 </dt> <dd class="basicInfo&#45;item value"> 求多源最短路径，求传递闭包 </dd> </dl>

目录

  1. 1 核心思路
  2. ▪ 路径矩阵
  3. ▪ 状态转移方程
  4. 2 算法过程
  5. 3 时间复杂度与空间复杂度
  1. 4 优缺点分析
  2. 5 算法描述
  3. 6 参考代码
  4. ▪ C语言
  5. ▪ C++语言
  1. ▪ Matlab源代码
  2. ▪ pascal语言
  3. ▪ java语言

Floyd算法核心思路

编辑

Floyd算法路径矩阵

通过一个图的权值 矩阵求出它的每两点间的 最短路径矩阵。
从图的带权 邻接矩阵A=[a(i,j)] n×n开始， 递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的 距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术（ 松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

Floyd算法状态转移方程

其 状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举 i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。

Floyd算法算法过程

编辑
1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i][j]表示从Vi到Vj需要经过的点，初始化D[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则D[i][j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

Floyd算法时间复杂度与空间复杂度

编辑
时间复杂度:O(n^3)；
空间复杂度:O(n^2) [1]  

Floyd算法优缺点分析

编辑
Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次 Dijkstra算法，也要高于执行|V|次 SPFA算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。

Floyd算法算法描述

编辑
a)　初始化：D[u,v]=A[u,v]
b)　For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
c)　算法结束：D即为所有点对的最短路径矩阵

Floyd算法参考代码

编辑

Floyd算法C语言

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<stdlib.h>
#define max 1000000000
 
int  d[1000][1000],path[1000][1000];
int  main()
{
     int  i,j,k,m,n;
     int  x,y,z;
     scanf ( "%d%d" ,&n,&m);
     
     for (i=1;i<=n;i++)
         for (j=1;j<=n;j++){
             d[i][j]=max;
             path[i][j]=j;
     }
     
     for (i=1;i<=m;i++) {
             scanf ( "%d%d%d" ,&x,&y,&z);
             d[x][y]=z;
             d[y][x]=z;
     }
     
     for (k=1;k<=n;k++)
         for (i=1;i<=n;i++)
             for (j=1;j<=n;j++) {
                 if (d[i][k]+d[k][j]<d[i][j]) {
                     d[i][j]=d[i][k]+d[k][j];
                     path[i][j]=path[i][k];
                 }
             }
     for (i=1;i<=n;i++)
         for (j=1;j<=i;j++)
           if  (i!=j)  printf ( "%d->%d:%d\n" ,i,j,d[i][j]);
     int  f, en;
     scanf ( "%d%d" ,&f,&en);
     while  (f!=en) {
         printf ( "%d->" ,f);
         f=path[f][en];
     }
     printf ( "%d\n" ,en);
     return  0;
}

Floyd算法C++语言

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<vector>
using  namespace  std;
const  int  &INF=100000000;
void  floyd(vector<vector< int > > &distmap, //可被更新的邻接矩阵，更新后不能确定原有边
            vector<vector< int > > &path) //路径上到达该点的中转点
//福利：这个函数没有用除INF外的任何全局量，可以直接复制！
{
     const  int  &NODE=distmap.size(); //用邻接矩阵的大小传递顶点个数，减少参数传递
     path.assign(NODE,vector< int >(NODE,-1)); //初始化路径数组 
     for ( int  k=1; k!=NODE; ++k) //对于每一个中转点
         for ( int  i=0; i!=NODE; ++i) //枚举源点
             for ( int  j=0; j!=NODE; ++j) //枚举终点
                 if (distmap[i][j]>distmap[i][k]+distmap[k][j]) //不满足三角不等式
                 {
                     distmap[i][j]=distmap[i][k]+distmap[k][j]; //更新
                     path[i][j]=k; //记录路径
                 }
}
void  print( const  int  &beg, const  int  &end,
            const  vector<vector< int > > &path) //传引用，避免拷贝，不占用内存空间
            //也可以用栈结构先进后出的特性来代替函数递归 
{
     if (path[beg][end]>=0)
     {
         print(beg,path[beg][end],path);
         print(path[beg][end],end,path);
     }
     else  cout<< "->" <<end;
}
int  main()
{
     int  n_num,e_num,beg,end; //含义见下
     cout<< "（不处理负权回路）输入点数、边数：" ;
     cin>>n_num>>e_num;
     vector<vector< int > > path,
           distmap(n_num,vector< int >(n_num,INF)); //默认初始化邻接矩阵
     for ( int  i=0,p,q; i!=e_num; ++i)
     {
         cout<< "输入第" <<i+1<< "条边的起点、终点、长度（100000000代表无穷大，不联通）：" ;
         cin>>p>>q;
         cin>>distmap[p][q];
     }
     floyd(distmap,path);
     cout<< "计算完毕，可以开始查询，请输入出发点和终点：" ;
     cin>>beg>>end;
     cout<< "最短距离为" <<distmap[beg][end]<< "，打印路径：" <<beg;
     print(beg,end,path);
}