Xinyang's Blog

All-pairs shortest path algorithm

问题描述

给定图 ，其中 为点集， 为边集。 表示连接 和 两点之间的边的权重，如果两点间没有边则为 。

求任意两个顶点 之间最短路径的长度 dist[i][j]。

算法思想

  • 首先我们考虑这样一个问题：找到一条长度尽可能短，并且跳转尽可能少的路径。具体来说，我们要求一个数组 dist[i][j][k]，表示在 和 这两个结点之间，最多经过 个点的最短路径长度。

    显然，当 时，也就是不经过任何点时， 和 之间的距离等于他们之间的边权 。

    而当时，到达 的路径可以被所有与 相连的点更新，即

    $2
    i
    ux
    j
    u1
    u2
    ...

    图中

    1
    2
    3
    4
    5
    6
    dist[i][j] <- w[i][j]
    for k = 1 to |V|:
        for i in V:
        	for j in V:
        		for u in V:
        			dist[i][j][k] <- min(dist[i][j][k-1], dist[i][u][k-1] + w[u][j])

    上面的算法怎么优化？

    • 滚动数组空间优化

      dist[i][j][k] <- dist[i][u][k-1] + w[u][j] new_dist[i][j] <- dist[i][u] + w[u][j]

    • 我们需要最外层循环吗？

      $2
      i
      p1
      j
      p2
      p3

      假设橙色为最短路，我们只执行一边上述循环的话，只能找到，找不到橙色的最短路。

      究其原因，是因为我们不能保证在更新dist[i][j]时，dist[i][ux]和dist[ux][j]已经是最短的。那么如果我们按照一定的顺序更新dist数组，使得我在更新到dist[i][j]时，所有的 的前驱结点 的dist[i][ux], dist[ux][j]已经更新好，那么我们是不是就不需要外层循环了呢？

    • 对比一下min(dist[i][j], dist[i][u] + w[u][j]) 和 矩阵乘法的内层：dist[i][j] + dist[i][u] * w[u][j])，发现它们有异曲同工之处

      矩阵乘法中，

      1
      2
      3
      4
      5
      for k = k * 2:
          for i in V:
                  for j in V:
                      for u in V:
                          dist[i][j][k] <- min(dist[i][j][k / 2], dist[i][u][k / 2] + dist[u][j][k / 2])

  • 另一种解法

    一条最短路径 一定包含0个或者若干个中间点。

    如果我们选择点集 中前 个点 作为中间点，那么它有一条很好的性质：

    1. 如果 的最短路径中不包含 ，那么

      $2
      i
      u
      j
      p2
      p3

    2. 如果 的最短路径中包含 ，那么

      $2
      i
      p1
      j
      p2
      u
      u1
       $2
      i
      p1
      j
      p2
      u
      u1

    所以我们可以写出状态转移方程

举例说明

伪代码

1
2
3
4
5
6
7
8
9
10
Floyd-Warshall(G{V,E}):
	for i = j:
		dist[i][j] <- 0
	for i != j
		dist[i][j] <- w[i][j]
	for k in V:
		for i in V:
			for j in V:
				dist[i][j] <- min(dist[i][j], dist[i][k] + dist[k][j])
				pre[i][j] <- pre[k][j] if dist[i][k] + dist[k][j] smaller

分析算法复杂度

  • 算法

    由于算法有3层循环，循环最内部复杂度为，所以复杂度为

  • 调用 次 算法

    • 没有堆优化

      1次：

      n次：

    • 加入堆优化

      1次：

      n次：

对比两种算法的时间复杂度， 算法在 的稀疏图上有一定优势。

但是， 算法能够处理含有负权边的情况，这一点优于 算法。