Floyd算法

简介

  Floyd‐Warshall算法（英语：Floyd‐Warshall algorithm或简写为Floyd algorithm），中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图（可以有负权重，但不可存在负权回路）的最短路径问题。Floyd算法与迪杰斯特拉算法或贝尔曼福特算法相比，能够一次性的求出任意两点之间的最短路径，后两种算法运行一次只能计算出给定的起点和终点之间的最短路径。当然，Floyd算法计算的时间也要高于后两种算法，其算法核心的步骤由三层循环构成。

算法复杂度

时间复杂度$O(n^3)$，$n$为点的个数

引入

  一些城市之间有公路，有些则没有，如下图。为了方便安排行程以及节省路费，游客需要提前知道任意两个城市之间的最短路径和路程。

  图中有4个城市，每天边上的数字代表了该段公路的路程，注意这里的公路都是单向的。在求解最短路径之前，我们需要用邻接矩阵D来存储这个图。

  比如$A1$到$A2$的路程为$35$，则$D(1, 2)$为$35$；$A2$到$A1$的路程为$36$，则$D(2,1)$为$36$；$A1$无法到达$A4$，则设置$D(1,4)$为无穷大$∞$；$A1$到他自己的距离为$0$，所以$D(1,1)$为$0$。接着用路由矩阵$R$来存储两点之间的最短路径。
  首先，如果任意两点之间不能经过第三个点时，很明显这些城市之间的最短路程就是初始路程，两个矩阵都不变。
  接着，假设任意两点之间只可以经过
$A1$，该怎么求任意两点之间的最短路径呢？只需判断$D(i,1) + D(1,j)$是否比$D(i,j)$小即可。$D(i,j)$表示从顶点i到顶点j的路程，$D(i,1) + D(1,j)$表示从i号顶点到$1$号顶点，再从$1$号顶点到$j$号顶点的路程之和。其中$i$和$j$都是$1\sim n$循环，$n$为顶点数，即图上的城市数量之和。

  例如原本$A4$无法直接到达$A2$，故$D(4,2)$为无穷大；现在可以从$A4$经过$A1$到达$A2$，路程之和为$105$，即符合条件：$\infty =D\left( 4,2 \right) >D\left( 4,1 \right) +D\left( 1,2 \right) =105$，因此我们可以对两个矩阵进行更新： $D\left( 4,2 \right) =105,R\left( 4,2 \right) =R\left( 4,1 \right) =1$， 。这里$R(4,2)=1$表示从顶点$4$到顶点$2$的最短路径是先经过顶点$1$。

  同理， $\infty =D\left( 4,3 \right) >D\left( 4,1 \right) +D\left( 1,3 \right) =155$，即原本$A4→A3=\infty$，现在经过$A1$中转后 ，于是$A4$到$A3$的最短路程变为$155$，$D(4,3) = 155，R(4,3) = R(4,1) = 1$

现在假设在允许经过$A1$中转的基础上，任意两点之间还可以经过$A2$中转，于是有：

原本：$A1→A3=85$，现在：$A1→A2→A3 =75$，满足$85 =D\left( 1,3 \right) >D\left( 1,2 \right) +D\left( 2,3 \right) =75$，故更新矩阵：$D(1,3) = 75, R(1,3) = R(1,2) = 2$

原本：$A3→A1=90$，现在：$A3→A2→A1 =77$，满足$90=D\left( 3,1 \right) >D\left( 3,2 \right) +D\left( 2,1 \right) =77$$，故更新矩阵：$D(3,1) = 77, R(3,1) = R(3,2) = 2$

原本：$A4→A1→A3=155$，现在：$A4→A1→A2→A3 =145$，满足$155 =D\left( 4,3 \right) >D\left( 4,1 \right) +D\left( 1,3 \right) =145$，故更新矩阵：$D(4,3) = 145, R(4,3) = R(4,1) = 1$

同理，在允许经过$A1$和$A2$中转的基础上，任意两点之间还可以经过$A3$中转，按照上文的方法，可以将邻接矩阵$D$和路由矩阵$R$更新为：

最后，允许经过全部顶点中转，可以得到最终的邻接矩阵$D$和路由矩阵$R$：

此时邻接矩阵$D$就是任意两点之间的最短路程矩阵，路由矩阵存储了对应的最短路径。举个栗子：求$A4$到$A3$的最短路径。

最短路程：$D(4,3) = 145$；
最短路径：$R(4,3) = 1, R(1,3) = 2, R(2,3) = 3$，故最短路径为$A4→A1→A2→A3$

例题

已知50个点之间相互连接信息见表求最短距离矩阵，最短路径。

50个点之间相互连接信息矩阵

Floyd.m

function [distance, route] = Floyd(A)
    % Floyd算法求最短路径
    % 输入：邻接矩阵x，数值型
    % 输出：最短路径的距离矩阵distance，路由矩阵route

    n = size(A, 1);
    distance = A;

    % 路由矩阵route记录最短路径
    for i = 1 : n
       for j = 1 : n
          route(i, j) = j; 
       end
    end

    % Floyd算法
    for k = 1 : n
        for i = 1 : n
            for j = 1 : n
                if distance(i, j) > distance(i, k) + distance(k, j)
                    distance(i, j) = distance(i, k) + distance(k, j);
                    route(i, j) = route(i, k);
                end
            end
        end
    end
end

displayPath.m

function path = displayPath(route, start, dest)
    % 打印出任意两点之间的最短路径
    % route : 路由矩阵
    % start : 起点index
    % dest : 终点index
    % path：最短路径
    path = [start];
    while 1
       if route(start, dest) ~= dest 
          start = route(start, dest);
          path = [path, start];
       else
           path = [path, dest];
           break;
       end
    end
end

main.m

%%
clear, close, clc

%% 初始距离矩阵
n = 50;
A = (ones(n, n) - eye(n, n)) * 100000;
A(1,2)=400;A(1,3)=450; A(2,4)=300;A(2,21)=230; A(2,47)=140;A(3,4)=600;
A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200; A(6,7)=320; A(6,8)=340;
A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285; A(9,10)=180; A(10,11)=150;
A(10,15)=160; A(11,12)=140; A(11,14)=130; A(12,13)=200; A(13,34)=400;
A(14,15)=190;A(14,26)=190; A(15,16)=170; A(15,17)=250; A(16,17)=140;
A(16,18)=130; A(17,27)=240; A(18,19)=204; A(18,25)=180; A(19,20)=140;
A(19,24)=175; A(20,21)=180; A(20,24)=190; A(21,22)=300; A(21,23)=270;
A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;
A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;
A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;
A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;
A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;
A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;
A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;
A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;
% 矩阵对称
for i = 1 : n
    for j = 1 : i - 1
        A(i, j) = A(j, i);
    end
end

%% 输出距离矩阵到文件
fid = fopen('primaryDistance.txt', 'w');
for i = 1 : n
    for j = 1 : n
        fprintf(fid, '%4d ', A(i,j));
    end
    fprintf(fid, "\n");
end
fclose(fid);

%%
clear, close, clc

%% 导入初始距离矩阵
load primaryDistance.txt
A = primaryDistance;
clear primaryDistance
n = size(A, 1);

%% 调用Floyd.m算法计算最短距离矩阵以及路由矩阵
[distance, route] = Floyd(A);

%% 将最短距离矩阵写入文件
fid=fopen('shortDistance.txt', 'w');
for i = 1 : n
    for j =1 : n
        fprintf(fid, '%4d ', distance(i,j));
    end
    fprintf(fid, "\n");
end
fclose(fid);

%% 将最短路径写入文件
fid=fopen('shortPath.txt', 'w');
for i = 1 : n
    for j = 1 : i
        if i == j
            continue;
        else
            path = displayPath(route, i, j);
            pathNumber = length(path);
            str = sprintf('(%d 到 %d 的最短路径长度为：%d) %d', i, j, distance(i, j), path(1));
            fprintf(fid, '%s', str);
            for k = 2 : pathNumber
                strTmp = sprintf(' -> %d', path(k));
                fprintf(fid, '%s', strTmp);
            end
            fprintf(fid, '\n');
        end
    end
end
fclose(fid);

部分结果

shortPath
shortDistance

---