OI:#2 最短路算法

最短路算法(Shortest Path Algorithm),是一种解决寻找图中两个顶点间最短路径的算法,比如说电子地图中的导航问题。

常用的最短路算法有 Floyd-WarshallDijkstra,和 Bellman-Ford 算法。

下面将分别对这三种算法进行讲解。

Floyd-Warshall 算法

中转点

首先引入一个中转点的概念。

在日常快递运输过程中,因为成本问题,很少有直接从一个城市发往另一个城市的车。为了控制成本,快递公司会一些城市中设一个物流转运中心。如 A市->B市 快递的路径可能是这样的:A市 -> M转运中心 -> N转运中心 -> B转运中心。

Floyd 中中转点的概念与此类似。

基本思想

Floyd 算法基于动态规划的思想。

对于每一个顶点 $A$,我们对每个图中剩余的顶点 $B$ 判断:

  • 如果引入一个中转点 $M$ ,$A \rightarrow M \rightarrow B$ 的路径长度是否短于 $A \rightarrow B$ 的路径长度?
    • 如果是的话,更新 $A \rightarrow B$ 的长度为 $A \rightarrow M \rightarrow B$ 的长度。

代码实现

Floyd 被称为一种 for - for - for 算法,所以由此可以看出 Floyd 的核心部分是一个三重循环。

int map[N][N];
// 存储路径长度
// map[A][B] 代表 A -> B 的最短长度

memset(map, 0x3f, sizeof map);
// 初始化所有路径长度为 INF 

for (int i = 1; i <= N; ++i) 
  map[i][i] = 0;
// 将自己到自己的路径长度设为 0

//
// >> 在这里读入数据
//

for (int i = 1; i <= N; ++i) 
  for (int j = 1; j <= N; ++j) 
    for (int k = 1; k <= N; ++k) 
      map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

// Floyd 核心算法

思考与探究

由上可以看出,Floyd 是一个极其简单的最短路算法。

我们思考如下几个问题:

该算法的复杂度如何?

可以明显地看出,Floyd 算法的时间复杂度为 $O(N^3)$,空间复杂度为 $O(N^2)$。
因此 Floyd 算法只适合处理小量的数据($N=500$ 量级)。

该算法与其它最短路算法的优势在哪里?

一个最大的优势在于 Floyd 是一个在线算法,即它支持动态修改数据(思考[1]:动态修改数据的时间复杂度为多少?)。
比如,P1119 灾后重建 - 洛谷 这题很好地运用了 Floyd 算法这一特性。

另一个优势是 Floyd 能求出任意两点之间的最短路径。

Dijkstra 算法

解答

[1]

答案:$O(N^2)$
解析:每新增一个点,相当于新增一个中转点。需要对所有的以当前的点为中转点进行更新距离操作。


本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!