多源多目标最短路径问题：更高效求解方法咨询

针对你提出的「从每个源节点到任意目标节点的最小权重最短路径」问题，朴素解法逐个跑Dijkstra的效率确实偏低，这里提供几个更高效的优化方案：

1. 反向图+单源最短路径（最优推荐） #

这是最常用的优化思路，核心是将多目标问题转化为单源问题：

• 步骤1：构建原图形的反向图——把所有边的方向反转，权重保持不变（比如原边u -> v权重w，改为v -> u权重w）。
• 步骤2：创建一个超级源节点S，给S添加到所有目标节点的边，权重设为0。
• 步骤3：以超级源节点S为起点，运行一次Dijkstra算法（如果图中存在负权边，改用Bellman-Ford或SPFA）。
• 步骤4：算法结束后，每个源节点的最短路径距离，就是原问题中该源节点到任意目标节点的最小权重路径长度；回溯路径的话，反向推导到目标节点即可。

这个方法只需要运行一次最短路径算法，时间复杂度为O(M + N log N)（N是节点数，M是边数），对比朴素解法的O(K*(M + N log N))（K是源节点数量），效率提升非常明显，尤其适合源/目标节点数量较多的场景。

比如你的例子：源节点A、B、C，目标节点D、E、F。构建反向图后，超级节点S连向D、E、F，跑一次Dijkstra就能直接得到A、B、C到最近目标节点的最短路径。

2. 批量Dijkstra算法 #

如果反向图的构建存在限制（比如边的方向性有特殊业务约束），可以用批量初始化的方式优化：

• 步骤1：初始化所有源节点的距离为0，其他节点距离为无穷大。
• 步骤2：将所有源节点同时加入优先队列（优先队列存储(当前距离, 节点)）。
• 步骤3：按照标准Dijkstra流程处理队列，每个节点被弹出时记录最短距离；同时可以维护前驱节点信息，用于回溯到目标节点的路径。
• 步骤4：遍历所有目标节点，对每个源节点筛选出最小的路径距离。

这个方法的时间复杂度和反向图方案接近，但实现上需要额外处理多源的距离跟踪，适合需要保留每个源节点到所有目标节点路径信息的场景。

3. Floyd-Warshall全局预处理 #

如果图的节点数量较小（比如N ≤ 500），可以提前预处理所有节点对的最短路径：

• 步骤1：初始化一个N×N的距离矩阵dist，dist[i][j]表示节点i到j的最短路径权重，初始时dist[i][j]为边的权重（无直接边则设为无穷大），dist[i][i] = 0。
• 步骤2：运行Floyd-Warshall算法，通过三重循环更新距离矩阵：

  for k in range(N):
      for i in range(N):
          for j in range(N):
              if dist[i][j] > dist[i][k] + dist[k][j]:
                  dist[i][j] = dist[i][k] + dist[k][j]
  

• 步骤3：预处理完成后，对每个源节点s，遍历所有目标节点t，取dist[s][t]的最小值即可。

这个方案的预处理时间复杂度是O(N³)，但查询阶段是O(1)，适合节点规模小、需要频繁查询的场景。

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