最短路径中超级源点的使用

1. 问题:

在最短路径问题中,如果源点有多个,我之前的做法可能都是遍历这n个源点

2. 背景题目

leetcode题目:大致意思如下

给定一个 01 矩阵 mat,输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
(斜对角的距离是2)
(简单理解就是地图上陆地每个位置到海洋的最短距离)

2.1之前的思考

遍历这个二维矩阵呗,对每个1进行一次BFS,求最短路径
但后来发现,假设有个A位置,则这个A可能不止一次的要被BFS访问到,因为他可能出现在很多结点的BFS路径上(比如这个A是海边的一个结点)

2.2 问题的简化

如果海洋只有一个点的话,问题就可以倒过来想了,海洋到所有陆地的最短距离(单个源点)

2.3 超级源点(超级0)

而当海洋面积变大的时候(多个源点),可以考虑设置一个超级源点super0,他到所有海洋(0)的距离都是1,
这时候,这些0其实就相当于从超级源点开始BFS后的第一步
这时候,每一个陆地(1)就只用被bFS跑一次了
并且,更重要的是,避免了多次使用BFS时遍历标记位的复杂考虑,总不能每个顶点都重置一次标记矩阵吧。。

2.4 具体实施

所有的0都相当于超级0进行BFS时的第一层,就直接double fori把所有0都压到队列里就ok了,然后一切照旧

上一篇:二叉树的BFS&打开转盘锁详解 -- 转载


下一篇:力扣1036.逃离大迷宫(Python题解)