如何计算多源Dijkstra热力图？多源点BFS实现方案咨询

多热力源热力图实现方案 #

你不需要分别运行多次单源BFS，也不用交替执行不同源的层级迭代，直接用多源BFS就可以一次性算出所有网格点到最近热力源的距离，效率比你提到的两种方案都要高。

核心逻辑 #

多源BFS和你现在用的单源层级BFS逻辑几乎一致，仅初始化步骤不同：

• 提前初始化一个距离矩阵，所有网格点的初始值设为无穷大（或你自定义的无效最大值）
• 初始化BFS队列时，把所有热力源点一次性加入队列的初始层，同时将这些源点的距离值设为0
• 按照你现有层级BFS的逻辑遍历整个网格：每次取出当前层的所有节点，遍历每个节点的相邻网格，若相邻网格的当前值大于新计算的距离值，就更新该网格的距离，再将其加入下一层队列
• 遍历完成后，距离矩阵的数值就是每个网格点到最近热力源的距离，直接将数值映射到你预设的热力色阶即可生成热力图

方案优势 #

• 时间复杂度为O(N)，N为网格总点数，和单源BFS时间复杂度一致，不受热力源数量影响，远优于多次单源BFS的O(k*N)（k为热力源数量）
• 天然保证每个网格点取到的是所有源的最小距离，不需要额外做全局最小值计算
• 实现简单，不需要修改你现有BFS的核心遍历逻辑，仅调整初始化步骤即可

自定义扩展 #

如果你的热力图需要支持不同源的差异化配置（比如不同源的初始热力值不同、距离衰减系数不同），只需要在初始化队列时给每个源点附加对应的权重参数，更新相邻节点数值时按对应规则计算即可，不需要调整BFS的遍历逻辑。

内容的提问来源于stack exchange，提问作者Steveit