图论模型——图论最短路径求解：弗洛伊德算法

个人学习笔记，课程为数学建模清风付费课程

目录

1.概述

2.最短路径应满足的结论

3.思考：怎么记录最短路径经过的点？

4.MATLAB代码 

5.Path矩阵怎么看 

6.打印指定两点间最短距离 

7.打印任意两点间最短路径 

8.思考题：求出任意两点间的最短路径

---

1.概述

       Floyd‐Warshall 算法（英语： Floyd‐Warshall algorithm 或简写为 Floyd algorithm），中文亦称弗洛伊德算法，是解决 任意两点间 的最短路径的一种算法，可以正确处理无向图或有向图（可以有负权重，但不可存在负权回路）的最短路径问题。

       Floyd 算法与迪杰斯特拉算法或贝尔曼福特算法相比，能够一次性的求出任意两点之间的最短路径，后两种算法运行一次只能计算出给定的起点和终点之间的最短路径。

       当然， Floyd 算法计算的时间也要高于后两种算法，其算法核心的步骤由三层循环构成

 

 

 2.最短路径应满足的结论

从上图中不难得到以下两个结论：

（ 1 ）如果某个节点（例如点 8 ） 位于 从起点 0 到终点 4 的最短路径上，那么：从 0 到 4 的最短路径的距离 =  从 0 到 8 的最短路径的距离 + 从 8 到 4 的最短路径的距离

（ 2 ）如果某个节点（例如点 3 ） 不在 从起点 0 到终点 4 的最短路径上，那么：从 0 到 4 的最短路径的距离 ≤ 从 0 到 3 的最短路径的距离 + 从 3 到 4 的最短路径的距离

（注：这里写 ≤ 号是因为我们最终求出来的最短路径的走法可能不唯一）

从上面观察到的两个结论中，我们不难提炼出下面这个思想：

假设现在有一个起点 A 和终点 B ，那么对于其他任意的中间点 M ：D(A,B) ≤ D(A,M) + D(M,B) 

这里， D(X,Y) 表示 X 和 Y 两点之间的最短距离。

因此， Floyd 算法实际上核心在于一个三层循环，下面给出 伪代码：

1 let dist be a |V|  × |V| array of minimum distances iniƟalized to ∞ (infinity)

V 是顶点的集合， |V| 表示顶点的个数，首先我们初始化最小距离矩阵 dist ，其中每一个元素都是Inf.

2 for each vertex v

3 dist[v][v] ← 0

将 dist 矩阵的主对角线元素变为 0.( 相同的点的最短距离当然是 0 喽 )

4 for each edge (u,v)

5 dist[u][v] ← w(u,v)  // the weight of the edge (u,v)

如果 u,v 两个顶点之间有权重，则用权重更新最短距离矩阵 . （事实上，1‐5 步就是在生成一个权重邻接矩阵）

6 for k from 1 to |V| 

中间节点 k 从 1‐ |V|  循环

7    for i from 1 to |V|

起始节点 i 从 1‐ |V|  循环

8       for j from 1 to |V|

终点节点 j 从 1‐ |V|  循环

9 if dist[i][j] > dist[i][k] + dist[k][j] 

如果 i,j 两个节点间的最短距离大于 i 和 k 的最短距离 +k 和 j 的最短距离

10 dist[i][j] ← dist[i][k] + dist[k][j]

那么我们就令这两个较短的距离之和取代 i,j 两点之间的最短距离

11 end if

结束 if 循环

( 引用来源：维基百科 )

3.思考：怎么记录最短路径经过的点？

以上的伪代码可以实现计算任意两点之间的最短路径的距离，那么： 这个最短路径经过哪些点我们能否通过另一个矩阵记录下来呢？

在视频中： https://www.bilibili.com/video/av54668527 ，我们确实看到了可通过一个路径矩阵path （视频中用的符号是 S ）来记录下这个过程。

下面我们就在我们的伪代码中加入这一功能：

1 let dist be a |V|  × |V| array of minimum distances iniƟalized to ∞ (infinity)

2 for each vertex v

3    dist[v][v] ← 0

4 for each edge (u,v)

5 dist[u][v] ← w(u,v)  // the weight of the edge (u,v)

在这里初始化路径矩阵 path( 里面的每一个元素用终点填充，即 path_ij=j ，另外，我们可以

令主对角线元素为 ‐1) ， path 是路径矩阵，其元素 path_ij 表示起点为 i ，终点为 j 的两个节点

之间的最短路径要经过的节点

6 for k from 1 to |V|

7    for i from 1 to |V|

8       for j from 1 to |V|

9          if dist[i][j] > dist[i][k] + dist[k][j] 

10 dist[i][j] ← dist[i][k] + dist[k][j]

在这个 if 语句中加入一行： path[i][j] ← path[i][k]

11         end if

4.MATLAB代码 

%% 首先将图转换为权重邻接矩阵D
n = 5;  %一共五个节点
D = ones(n) ./ zeros(n);  % 全部元素初始化为Inf
for i = 1:n
    D(i,i) = 0;  % 主对角线元素为0
end
D(1,2) = 3;
D(1,3) = 8;
D(1,5) = -4;
D(2,5) = 7;
D(2,4) = 1;
D(3,2) = 4;
D(4,3) = -5;
D(5,4) = 6;
D(4,1) = 2;
 
%% 调用Floyd_algorithm函数求解
[dist,path] = Floyd_algorithm(D)
 
print_path(path,dist,1,5)
print_path(path,dist,1,4)
print_path(path,dist,3,1)
 
clc
disp('下面我们打印任意两点之间的最短距离：')
print_all_path(D)

function [dist,path] = Floyd_algorithm(D)
%% 该函数用于求解一个权重邻接矩阵任意两个节点之间的最短路径
% 输入：
%        D是权重邻接矩阵
% 输出：
%        dist是最短距离矩阵，其元素dist_ij表示表示i,j两个节点的最短距离
%        path是路径矩阵，其元素path_ij表示起点为i，终点为j的两个节点之间的最短路径要经过的节点
 
n = size(D,1);  % 计算节点的个数
 
% 初始化dist矩阵
dist = D;
 
% 下面我们来初始化path矩阵
path = zeros(n);
for j = 1:n
    path(:,j) = j;   % 将第j列的元素变为j
end
for i = 1:n
    path(i,i) = -1;  % 将主对角线元素变为-1
end
 
% 下面开始三个循环
for k=1:n    % 中间节点k从1- n 循环
   for i=1:n     % 起始节点i从1- n 循环
      for j=1:n    % 终点节点j从1-n 循环
          if dist(i,j)>dist(i,k)+dist(k,j)  % 如果i,j两个节点间的最短距离大于i和k的最短距离+k和j的最短距离
             dist(i,j)=dist(i,k)+dist(k,j);  % 那么我们就令这两个较短的距离之和取代i,j两点之间的最短距离
             path(i,j)=path(i,k);   % 起点为i，终点为j的两个节点之间的最短路径要经过的节点更新为path(i,k)
             % 注意，上面一行语句不能写成path(i,j) = k; 这是网上很多地方都容易犯的错误，在PPT11页中会告诉大家为什么不能这么写
          end
      end
   end
end
 
end

Dist举证：表示从起点到终点的最短路径

代码中的一句话：

path(i,j)=path(i,k);

注意，上面一行语句不能写成path(i,j) = k; 

 我们将代码中的path(i,j)=path(i,k)改成path(i,j) = k，得到如下结果：

dist矩阵和原来的相同 path矩阵的部分元素和原来不同

5.Path矩阵怎么看 

从3到1的最短路径：3->2->4->1

6.打印指定两点间最短距离 

function [] = print_path(path,dist,i,j)
%% 该函数的作用是打印从i到j经过的最短路径
% 输入：
%        path是使用floyd算法求出来的路径矩阵
%        dist是使用floyd算法求出来的最短距离矩阵
%        i是起始节点的编号
%        j是终点节点的编号
% 输出：无
 
if i == j
    warning('起点和终点相同，请检查后重新输入')  % 在屏幕中提示警告信息
    return;  % 不运行下面的语句，直接退出函数
end
if path(i,j) == j   % 如果path(i,j) = j，则有两种可能：
% （1）如果dist(i,j) 为 Inf , 则说明从i到j没有路径可以到达
    if dist(i,j) == Inf
        disp(['从',num2str(i),'到',num2str(j),'没有路径可以到达'])
% （2）如果dist(i,j) 不为 Inf , 则说明从i到j可直接到达，且为最短路径
    else
        disp(['从',num2str(i),'到',num2str(j),'的最短路径为'])
        disp([num2str(i),' ---> ',num2str(j)])
        disp(['最短距离为',num2str(dist(i,j))])
    end
else  % 如果path(i,j) ~= j，则说明中间经过了其他节点：
    k = path(i,j);
    result = [num2str(i),' ---> '];  % 初始化要打印的这个字符串
    while k ~= j  % 只要k不等于j, 就一直循环下去
        result = [result , num2str(k) , ' ---> ' ];  % i先走到k这个节点处
        k = path(k,j);
    end
    result = [result , num2str(k)];
    disp(['从',num2str(i),'到',num2str(j),'的最短路径为'])
    disp(result)
    disp(['最短距离为',num2str(dist(i,j))])
end
 
end

7.打印任意两点间最短路径 

function [] = print_all_path(D)
%% 该函数的作用是求解一个权重邻接矩阵任意两个节点之间的最短路径,并打印所有的结果出来
% 输入：
%        D是权重邻接矩阵
% 输出：无
 
[dist,path] = Floyd_algorithm(D);   % 调用之前的Floyd_algorithm函数
n = size(D,1);
if n == 1
    warning('请输入至少两阶以上的权重邻接矩阵')   % 在屏幕中提示警告信息
    return;   % 不运行下面的语句，直接退出函数
end
 
for i = 1:n
    for j = 1:n
        if i ~= j  % 不等号用~=表示
            print_path(path,dist,i,j);   % 调用之前的print_path函数
            disp('-------------------------------------------')
            disp('  ')
        end
    end
end
 
end

部分结果展示如下：

 

8.思考题：求出任意两点间的最短路径

% 思考题的参考答案
%% 首先将图转换为权重邻接矩阵D
n = 9;  %一共九个节点
D = zeros(n);  % 全部元素初始化为0, 等会你们就知道为什么这样设置啦
% 因为是无向图，所以权重邻接矩阵是一个对称矩阵
D(1,2) = 4; D(1,8) = 8; 
D(2,8) = 3; D(2,3) = 8;
D(8,9) = 1; D(8,7) = 6; 
D(9,7) = 6; D(9,3) = 2;
D(7,6) = 2; D(3,4) = 7; 
D(3,6) = 4; D(6,4) = 14;
D(4,5) = 9; D(6,5) = 10;
D = D+D';   % 这个操作可以得到对称矩阵的另一半
for i = 1:n
    for j = 1:n
        if (i ~= j) && (D(i,j) == 0)  
            D(i,j) = Inf;   % 将非主对角线上的0元素全部变为Inf
        end
    end
end
 
%% 调用Floyd_algorithm函数求解
[dist,path] = Floyd_algorithm(D)