数学建模更新6（Floyd算法（弗洛伊德算法））_floyd循环检测算法数学模型

一.概述

弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图（可以有负权重，但不可存在负权回路）的最短路径问题
Floyd算法与迪杰斯特拉算法或贝尔曼福特算法相比，能够一次性的求出任意两点之间的最短路径，后两种算法运行一次只能计算出给定的起点和终点之间的最短路径

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

从上图中不难得到以下两个结论：
（1）如果某个节点（例如点8）位于从起点0到终点4的最短路径上，那么：
从0到4的最短路径的距离 = 从0到8的最短路径的距离 +从8到4的最短路径的距离
（2）如果某个节点（例如点3）不在从起点0到终点4的最短路径上，那么：
从0到4的最短路径的距离 ≤ 从0到3的最短路径的距离 +从3到4的最短路径的距离
（注：这里写≤号是因为我们最终求出来的最短路径的走法可能不唯一）

三.Floyd算法（弗洛伊德算法）

1.代码

从上面观察到的两个结论中，我们不难提炼出下面这个思想：
假设现在有一个起点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)
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)
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]
11 end if
(引用来源：维基百科)
1
2
3
4
5
6
7
8
9
10
11
12

2.伪代码详解

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循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.优化（记录最短路径的点）

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.转化为Matlab

%% 该函数用于求解一个权重邻接矩阵任意两个节点之间的最短路径
% 输入：
% D是权重邻接矩阵
% 输出：
% dist是最短距离矩阵，其元素dist_ij表示表示i,j两个节点的最短距离
% path是路径矩阵，其元素path_ij表示起点为i，终点为j的两个节点之间
的最短路径要经过的节点
1
2
3
4
5
6
7

5.结果分析

%% 首先将图转换为权重邻接矩阵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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

path矩阵：
从3到1的最短路径为： 3 ‐‐‐> 2 ‐‐‐> 4 ‐‐‐> 1

情况一：如果path(i,j)等于j，则有两种可能： （1）如果dist(i,j) 为 Inf , 则说明从i到j没有路径可以到 达；（2）如果dist(i,j) 不为 Inf , 则说明从i到j可直接到达， 且为最短路径。 情况二：如果path(i,j)不等于j，等于k： 这意味这从i到j的最短路径上要先从i经过k点，接着我 们需要判断path(k,j)是否等于j，如果等于j则下一步直 接从k点走到j点；否则就重复这个步骤循环下去，直 到走到j点结束。

打印指定两点间最短路径
function [] = print_path(path,dist,i,j)
%% 该函数的作用是打印从i到j经过的最短路径
% 输入：
% path是使用floyd算法求出来的路径矩阵
% dist是使用floyd算法求出来的最短距离矩阵
% i是起始节点的编号
% j是终点节点的编号
% 输出：无
print_path.m
2 1 3 5 4
1
2
3
4
5
6
7
8
9
10
11