Loading...
墨滴

进击的土豆同学

2021/08/30  阅读:29  主题:默认主题

最短路径—弗洛伊德算法(Floyd)

弗洛伊德算法(Floyd)

上一篇文章介绍了迪杰斯特拉算法(Dijkstra)。具体请看:最短路径算法——简单明了的迪杰斯特拉算法(Dijkstra)。Dijkstra适用于非负权图,并且一次只能从网络中找源点到任何一个节点的最短路径,而Floyd算法的应用更加广泛,可以求网络中任意两点之间的最短路径,而且弗洛伊德算法适用于负权图,这篇文章就用图和表的形式来介绍一下弗洛伊德算法!

1 思想(原理)

Floyd算法可以给出网络中任意两个节点之间的最短路径,因此它是比Dijkstra更一般的算法。Floyd算法的思想是将 个节点的网络表示为 列的矩阵,而矩阵中的元素 表示从节点 到节点 的距离 ,如果两点直接没有边相连,则相应的元素就是无穷 .

2 步骤

<1> 第0步:定义初始距离矩阵 、节点序列矩阵 ,如下表。对角线上用”—“表示不需要从自身到自身。

这里的节点序列矩阵相当于路线表,如下表, 表示,从节点 到节点 只需经过节点 即可。

.

<2> 一般的第k步:令第 行为枢轴行,第 列为枢轴列。对于矩阵 (上一步完成后的矩阵)中对的每一个元素做三重操作

如果满足条件: ,其中(i≠k,j≠k,i≠j)

则进行下面的操作:

<\a> 用 代替矩阵 中的元素 ,从而得到矩阵 .

<\b> 用 代替矩阵 中的元素 ,从而得到矩阵 .

<\c> 令 ,如果 ,停止,否则重复<2>.

3 栗子

直接看方法步骤会感觉太抽象,这里用一个例子进行步骤的演示. 对下图中的网络,求任意两个节点之间的最短路径,图中弧上给出了相应节点间的距离。弧(3,5)是有向的,其他边都是双边。

迭代0:矩阵 代表初始的网络。可以看到矩阵 除了 外(因为弧(3,5)是单向弧), 是对称的。

迭代1:令 . 矩阵中的黄色阴影表示的第1行和第1列为枢轴行和枢轴列。根据三重操作发现可以改进的元素是 ,即

(1) ,则在 中用 代替 ,并令 . (2) ,则在 中用 代替 ,并令 .

此时得到 ,得到下表

迭代2:令 . 矩阵中的黄色阴影表示的第2行和第2列为枢轴行和枢轴列。根据三重操作发现可以改进的元素是 ,即

(1) ,则在 中用 代替 ,并令 . (2) ,则在 中用 代替 ,并令 .

此时得到 ,得到下表 迭代3:令 . 矩阵中的黄色阴影表示的第3行和第3列为枢轴行和枢轴列。根据三重操作发现可以改进的元素是 ,即

(1) ,则在 中用 代替 ,并令 . (2) ,则在 中用 代替 ,并令 .

此时得到 ,得到下表 迭代4:令 . 矩阵中的黄色阴影表示的第4行和第4列为枢轴行和枢轴列。根据三重操作发现可以改进的元素是 ,即 (1) ,则在 中用 代替 ,并令 . (2) ,则在 中用 代替 ,并令 . (3) ,则在 中用 代替 ,并令 . (4) ,则在 中用 代替 ,并令 . (5) ,则在 中用 代替 ,并令 . (6) ,则在 中用 代替 ,并令 . (7) ,则在 中用 代替 ,并令 . (8) ,则在 中用 代替 ,并令 .

此时得到 ,得到下表

迭代5:令 . 矩阵中的黄色阴影表示的第5行和第5列为枢轴行和枢轴列。根据三重操作发现没有可以改进的元素了。

因此,最后得到的矩阵为:

这两个矩阵包含了网络中任意两个节点最短路径的所有信息。如从矩阵 中可以看出节点1到节点5的最短路径长度为12.从矩阵 中发现,节点1到节点5的中间节点是节点4,即节点1→节点4→节点5,再看节点1→节点4中间是节点2,即节点1需要通过节点2到达节点4,即节点1→节点2→节点4;而节点4可以直接到节点5,中间没有节点,因此可以得到节点1到节点5的最短路径是节点1→节点2→节点4→节点5.

进击的土豆同学

2021/08/30  阅读:29  主题:默认主题

作者介绍

进击的土豆同学