图 - 最短路径的定义及实现算法（二）
- 4 mins数据结构与算法系列（五十一）
昨天我们介绍了网图的最短路径定义，以及如何通过迪杰斯特拉算法实现，今天我们介绍最短路径的另一种常见实现算法 —— 弗洛伊德（Floyd）算法。
弗洛伊德算法的基本思想如下：
从任意节点 A 到任意节点 B 的最短路径不外乎两种可能，一种是直接从 A 到 B，一种是从 A 经过若干个节点到 B，所以，我们假设 dist(A,B) 为节点 A 到节点 B 的最短路径的距离，对于每一个节点 K，我们检查 dist(A,K) + dist(K,B) < dist(A,B) 是否成立，如果成立，证明从 A 到 K 再到 B 的路径比 A 直接到 B 的路径短，我们便设置 dist(A,B) = dist(A,K) + dist(K,B)，这样一来，当我们遍历完所有节点 K，dist(A,B) 中记录的便是 A 到 B 的最短路径的距离。
很简单吧！还是在 EdgeWeightedGraph 类中，我们将上述算法思路转化为代码如下：
// 通过弗洛伊德算法实现最短路径
public function floyd()
{
$path = []; // 路径，$path[$i][$j]=$k表示顶点i到顶点j的最短路径会经过顶点k。
$dist = []; // 长度数组，即$dist[$i][$j]=$sum表示顶点i到顶点j的最短路径的长度是$sum。
// 初始化
for ($i = 0; $i < $this->vNum; $i++) {
for ($j = 0; $j < $this->vNum; $j++) {
$dist[$i][$j] = $this->getWeight($i, $j); // 顶点i到顶点j的路径长度为i到j的权值。
$path[$i][$j] = $j; // 顶点i到顶点j的最短路径是经过顶点j。
}
}
// 计算最短路径
for ($k = 0; $k < $this->vNum; $k++) {
for ($i = 0; $i < $this->vNum; $i++) {
for ($j = 0; $j < $this->vNum; $j++) {
// 如果经过下标为k顶点路径比原两点间路径更短，则更新$dist[$i][$j]和$path[$i][$j]
$tmp = ($dist[$i][$k] == INF || $dist[$k][$j] == INF) ? INF : ($dist[$i][$k] + $dist[$k][$j]);
if ($dist[$i][$j] > $tmp) {
// i到j最短路径对应的值为更小的一个(即经过k的路径)
$dist[$i][$j] = $tmp;
// i到j最短路径对应的路径经过k
$path[$i][$j] = $path[$i][$k];
}
}
}
}
// 打印最短路径的结果
printf("floyd: \n");
for ($i = 0; $i < $this->vNum; $i++) {
for ($j = 0; $j < $this->vNum; $j++) {
printf("%2d ", $dist[$i][$j]);
}
printf("\n");
}
}
代码实现也非常简单，容易理解。我们为上述代码编写测试代码如下：
// 顶点和边数据
$nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
$edges = [
['A', 'B', 12],
['A', 'F', 16],
['A', 'G', 14],
['B', 'C', 10],
['B', 'F', 7],
['C', 'D', 3],
['C', 'E', 5],
['C', 'F', 6],
['D', 'E', 4],
['E', 'F', 2],
['E', 'G', 8],
['F', 'G', 9],
];
// 构造无向连通网
$graph = new EdgeWeightedGraph(count($nodes));
foreach ($nodes as $i => $v) {
$graph->addVertex($i, $v);
}
foreach ($edges as $edge) {
$start = $graph->getPosition($edge[0]);
$end = $graph->getPosition($edge[1]);
$graph->addEdge($start, $end, $edge[2]);
}
// 计算任意两个顶点间的最短路径
$graph->floyd();
运行这段测试代码，执行结果如下：
弗洛伊德算法计算的是任意顶点间的最短路径，所以生成的结果是一个矩阵，我们取第一行结果，即顶点 A 到任意其它顶点的最短路径，和上一篇通过迪杰斯特拉算法计算的结果完全一致。
很显然，弗洛伊德算法实现包含三层循环，对应的算法时间复杂度也是 O(n^3)，但是实现起来更简单，适用于需要计算所有顶点间的最短路径这种场景；迪杰斯特拉还可以计算指定顶点到其他顶点的最短路径，时间复杂度只有 O(n^2)，所以这种情况下使用迪杰斯特拉算法更合适。