> For the complete documentation index, see [llms.txt](https://wtifs.gitbook.io/diva-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wtifs.gitbook.io/diva-notes/algorithm/zui-duan-lu-jing.md).

# 最短路径

基本都是如下思路：

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

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

## Floyd 弗洛伊德算法

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

时间复杂度 `O(N^3)`

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

```go
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](https://leetcode.com/problems/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](https://leetcode.com/problems/network-delay-time)

## Bellman-Ford 算法

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

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

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

```go
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)
    }
}
```