图论：Floyd算法

【 1. Floyd算法简介 】

• 背景
  Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
• 用途
  Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负，但不许有包含带负权值的边组成的回路。
• 复杂度
  时间复杂度：$O(n^3)$，时间复杂度比较高，不适合计算大量数据。
  空间复杂度：$O(n^2)$
  由于三重循环结构紧凑，对于稠密图，效率要高于执行 n 次Dijkstra算法。
• 算法思想原理：动态规划

1. 首先我们的目标是寻找从点 i 到点 j 的最短路径。
2. 然后我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）：从任意节点 i 到任意节点 j 的最短路径不外乎2种可能，1是直接从 i 到 j，2是从 i 经过若干个节点 k 到 j 。
3. 所以，我们假设 Dis(i,j) 为节点 i 到节点 j 的最短路径的距离，对于每一个节点 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 的最短路径的距离。
4. 算法核心

for(k=1;k<=n;k++)
{
	for(i=1;i<=n;i++)
    {
     	for(j=1;j<=n;j++)
        {
        	if(Dis[i][k]+Dis[k][j]<Dis[i][j])
             {
              	Dis[i][j]=Dis[i][k]+Dis[k][j];
                path[i][j]=path[i][k];
              }
         }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

【 2. 算法实现案例 】

• 求到任意一点到另一点的最短路径
  

• 若两点间不可直达（需经过第三点），则令两点距离为 ∞ 。
  创建Dis矩阵，Dis[i][j]：点 i 到点 j 的距离。
  创建Path矩阵，Path[i][j]：点 i 到点 j 的最短路径中，点 i 的下一个点，默认为-1。
  

• 顶点1为中间点时
  2→1→3距离∞+6=∞ >3 ，不更新表格。
  2→1→4距离∞+4=∞=∞ ，不更新表格。
  3→1→2距离7+2=9 < ∞ ，更新表格。
  3→1→4距离7+4=11 > 1 ，不更新表格。
  4→1→2距离5+2=7 < ∞ ，更新表格。
  4→1→3距离5+6=11 < 12 ，更新表格。
  

• 顶点2为中间点时
  1→2→3距离2+3=5 <6 ，更新表格。
  1→2→4距离2+∞=∞>4 ，不更新表格。
  3→2→1距离9+∞=∞ >7 ，不更新表格。
  3→2→4距离9+∞=∞ > 1 ，不更新表格。
  4→2→1距离7+∞=∞ > 5 ，不更新表格。
  4→2→3距离7+1=10 < 11 ，更新表格。
  

• 顶点3为中间点时
  1→3→2距离5+9=14 > 2 ，不更新表格。
  1→3→4距离5+1=6 > 4 ，不更新表格。
  2→3→1距离3+7=10 < ∞ ，更新表格。
  2→3→4距离3+1=4 < ∞ ，更新表格。
  4→3→1距离10+7=17 > 5 ，不更新表格。
  4→3→2距离10+9=19 > 7 ，不更新表格。
  

• 顶点4为中间点时
  1→4→2距离4+7=11 > 2 ，不更新表格。
  1→4→3距离4+10=14 > 5 ，不更新表格。
  2→4→1距离4+5=9 < 10 ，更新表格。
  2→4→3距离4+10=14 > 3 ，不更新表格。
  3→4→1距离1+5=6 < 7 ，更新表格。
  3→4→2距离1+7=8 < 9 ，更新表格。
  

• 由上述，已遍历完所有点，得到以下最短路径
  
  例如：
  点2到点3的最短距离为3，最短路径为2→3。
  点1到点3的最短距离为5，最短路径为1→2→3。

【 3. Floyd 算法的 C 描述 】

/**** **** **** **** **** ****
*    Function Name :        全源最短路径(Folyd算法)
*    Description :       		DP, O(N^3)
**** **** **** **** **** ****/ 
//初始化
//path[i][j]=j;
void Floyd()
{  int i,j,k;
    for(k=0;k<vertex_number;k++) {
        for(i=0;i<vertex_number;i++) {
            for(j=0;j<vertex_number;j++) {
                if((graph[i][k]==-1) || (graph[k][j]==-1))     continue;
                if((graph[i][j]==-1) || (graph[i][j] > graph[i][k]+graph[k][j]))
                {
                    graph[i][j] = graph[i][k]+graph[k][j];   /*最短路径值*/ 
                    path[i][j] = k;     /*最短路径*/ }}}}}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

【 4. Floyd 算法的 Matlab 描述 】

tulun2.m
a= [ 0,50,inf,40,25,10;
     50,0,15,20,inf,25;
     inf,15,0,10,20,inf;
     40,20,10,0,10,25;
     25,inf,20,10,0,55;
     10,25,inf,25,55,0];
[D, path]=floyd(a)

floyd.m
function [D,path,min1,path1]=floyd(a,start,terminal)
D=a;n=size(D,1);path=zeros(n,n);
for i=1:n
   for j=1:n
      if D(i,j)~=inf
         path(i,j)=j;
      end, 
   end,
end
for k=1:n
   for i=1:n
      for j=1:n
         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);
         end, 
      end, 
   end,
end
if nargin==3
   min1=D(start,terminal);
   m(1)=start;
   i=1;
   path1=[ ];   
   while   path(m(i),terminal)~=terminal
      k=i+1;                                
      m(k)=path(m(i),terminal);
      i=i+1;
   end
   m(i+1)=terminal;
   path1=m;
end   

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