最短路径

基本都是如下思路：

对起点 i 和终点 j，遍历中间节点 k

dist[i,j] = min(dist[i,j], dist[i,k] + dist[k,j])

Floyd 弗洛伊德算法

三层 for 循环，第一层遍历中间节点 k，第二次遍历起点 i，第三次遍历终点 j，不断更新起点到终点的值。

时间复杂度 O(N^3)

允许边为负值，但环的路径和不能为负值。否则沿环一直走就会累加到无限负值。

for k := range dist {
    for i := range dist {
        for j := range dist {
            dist[i,j] = min(dist[i,j], dist[i,k] + dist[k,j])
        }
    }
}

例题

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Dijkstra 迪杰斯特拉算法

单源最短路径算法。通过 Dijkstra 计算图中的最短路径时，需要指定起点 s (即从顶点 s 开始计算)

此外，引进两个集合 A 和 B。A 保存已求出最短路径的顶点，B 则是剩下的点。

不允许边为负值。

操作步骤

1. 初始时，A 只包含起点 s, 用一个最小堆来记录 B，其初始值为与 A 相连的边

2. 从堆中选出边长度最短的顶点 k，将 k 移入 A

3. 以 k 为中间节点，重新计算和 k 相邻的各节点到到 s 的距离，并将这些节点放到堆里候选

例题

743. Network Delay Time

Bellman-Ford 算法

这个像 Floyd 和 Dijkstra 的混合版本。也是单源最短路径算法。

其理论基础是，对一个有 N 个节点的图，从某个起点到终点，最多经过 N 个节点。

因此对图中最长的那条路径，更新 N 次，就一定能算出这条路径的长度。其余的路径比它还短，在此之前就就可以一块顺便算出来。

var dist []int // 表示从起点到每个节点的路径
for i := 0; i < N; i++ {
    for _, edge := range edges {
        u, v, weight := edge[0], edge[1], edge[2]
        dist[u] = min(dist[u], dist[v] + weight)
    }
}