前言
在图论与网格问题中，最常见的一类题目就是'求最短距离'。通常情况下，我们会从某一个起点出发，利用 BFS（广度优先搜索）逐层扩展，得到从该点到所有点的最短路。然而，在许多实际场景中，往往存在多个起点：例如从多个水源扩展到所有陆地、从多个火源蔓延到整个森林，或者像 LeetCode 1162. 地图分析中，从所有陆地出发，计算到最远海洋的距离。 这类问题的核心思想就是 BFS 多源最短路。它与单源 BFS 不同的地方在于：将所有起点一开始就同时加入队列，作为 BFS 的第一层；在层层扩展的过程中，天然保证了最短路的正确性；代码实现上非常简洁，不需要额外的多次 BFS。
前提引入
- 图可以有方向/无方向；边可以有权重（花费/距离/时间）。
- 最短路：从 A 到 B 的最小代价之和。
常见几种场景：
- 单源最短路（SSSP）：从一个起点 s 到所有点的最短路。
- 多源最短路（两种含义）：
- 多起点→所有点：有好几个起点，一起'向外扩散'；
- 任意两点（全源/全对，APSP）：所有点到所有点的最短路。
多源最短路两种玩法
多起点 → 所有点（常见于'多个出发点最近距离'）
- 无权图：把所有起点一起入队，做一次 BFS。
- 有权非负：把所有起点 dist=0，一起入堆，做一次 Dijkstra。
- 有负边：加一个超级源点 S，连向每个起点一条权重为 0 的边，然后 Bellman–Ford 或其他方案。
谈谈多源最短路
如何解决：
- 暴力，把多源最短路问题转换成若干个单元最短路问题，大概率会超时。
- 把所有的源点当成一个'超级源点'，问题就变成了单一的单源最短路问题。
从理性角度需要严谨的证明，从感性理解上，就是多个起点出发，向外扩展时，舍劣取优。
在代码层面，把所有的起点加入到队列里面，一层一层的向外扩展。
题目实练
542. 01 矩阵
给定一个由 0 和 1 组成的矩阵 mat，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1。
- 一个一个位置求，每个位置来一趟 BFS，这样子会超时的。
- 多源 BFS+ 正难则反，把所有的 0 当做起点，1 当做终点，这样 1 的位置就直接填结果，按照原先 1 找 0 还有倒退写值。 把所有的 0 加入到队列中，一层一层的向外扩展即可。
