最短路算法

最短路算法指的是在图G=(V,E)中，寻找从一个点s到另一个点d所有路径中最短的路径。

无权图-广度优先搜索

对于每条路都是无权的情况下（每条路等价），我们只用简单的宽度优先搜索，就可以解决问题。很简单，稍微注意一下用一个visited保存已经遍历过的点避免重复即可。

有权图-dijkstra/floyd

如果路是有权的，且每条边的权是非负的，可以用dijkstra算法。而floyd适用于任何图，不管有向无向，边权正负，但是最短路必须存在。

应用这两个算法，我们可以求出一个点s到所有点到最短路。

Floyd算法

我们定义一个数组 f[k][x][y]，表示只允许经过结点 1 到 k（也就是说，在子图 "V'={1, 2, ..., k}" 中的路径，注意，x 与 y 不一定在这个子图中），结点 x 到结点 y 的最短路长度。很显然，f[n][x][y] 就是结点 x到结点 y 的最短路长度。

f[0][x][y]：x 与 y 的边权，或者 0，或者 +inf（对应有边，相同点，无边的情况）。

然后采用递推，（f[k-1][x][y]，为不经过k点的最短路径，而 f[k-1][x][k]+f[k-1][k][y]，为经过了 k 点的最短路）

for (k = 1; k <= n; k++) {
  for (x = 1; x <= n; x++) {
    for (y = 1; y <= n; y++) {
      f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
    }
  }
}

事实上，可以证明，数组的第一维是可以省略的。因此代码可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])。可以发现对f[0][x][y]的初始化就变成了图的邻接矩阵。

例题代码，时间复杂度为\(O(n^3)\)，空间复杂度为\(O(n^2)\)：

INF = 60000000
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, K: int) -> int:
        # 初始化数组 f
        f = [[INF for _ in range(0, n+1)] for _ in range(0, n+1)]
        for time in times:
            f[time[0]][time[1]] = time[2]
        for i in range(1,n+1):
            f[i][i] = 0
        # 递推子图规模k
        for k in range(1, n+1):
            for x in range(1, n+1):
                for y in range(1, n+1):
                    f[x][y] = min(f[x][y], f[x][k] + f[k][y])
        # 返回题设的结果
        time = max(f[K][i] for i in range(1,n+1))
        return time if time != INF else -1

Dijkstra算法

将结点分成两个集合：已确定最短路长度的点集（记为 \(S\) 集合）的和未确定最短路长度的点集（记为 \(T\) 集合）。一开始所有的点都属于 \(T\) 集合。

初始化 dis(s)=0 ，其他点的 dis[d] 均为inf。dis[d]代表s到d的最短路长度。

然后重复这些操作：

从 \(T\) 集合中，选取一个最短路长度最小的结点，移到 \(S\) 集合中。
1. 可以使用堆来优化这个找最短的过程。
对那些刚刚被加入 \(S\) 集合的结点的所有出边执行松弛操作。
1. 松弛操作：对于边(u,v)，dis[v] = min(dis[v], dis[u] + w[u,v])。含义是，我们使用已知最短路的dis(u)，尝试通过s -> u -> v去更新所有v。

直到 \(T\) 集合为空，算法结束。

例题代码，使用最朴素的找最短过程，使用邻接矩阵，时间复杂度为\(O(n^2)\)：

INF = 60000000
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        f = [[INF for _ in range(0, n+1)] for _ in range(0, n+1)]
        for x,y,time in times:
            f[x][y] = time
        dis = [INF] * (n+1)
        dis[k] = 0

        T = set(range(1,n+1))
        for i in range(1, n+1):
            u = min(T, key=lambda i: dis[i])
            T.remove(u)
            for v in range(1, n+1):
                dis[v] = min(dis[v], dis[u] + f[u][v])

        ans = max(dis[1:])
        return ans if ans != INF else -1