如何基于不可修改的Dijkstra算法求解无向带权图的所有最短路径

你的初始思路确实能找到部分最短路径，但存在效率低、可能漏解的问题——比如当多条最短路径共享某条边时，第一次删除该边后，后续无法再找到依赖这条边的其他最短路径。这里有个更高效且准确的方案，全程只需要调用一次Dijkstra：

1. 调用Dijkstra获取核心数据
   先运行一次Dijkstra算法，得到源点S到所有节点的最短距离数组dist[]，以及目标点T的最短距离dist[T]。这一步是核心，所有合法的最短路径总权重必须等于dist[T]。

2. 构建最短路径子图
   遍历原图的所有边(u, v)（无向图所以每条边双向检查），仅保留满足以下条件的边：

   • dist[u] + weight(u,v) == dist[v]（从u到v的边能构成u到v的最短路径段）
   • 或者 dist[v] + weight(u,v) == dist[u]（从v到u的边能构成v到u的最短路径段）
     这个子图里只包含所有可能属于最短路径的边，完全剔除了无关边，大幅缩小了后续搜索范围。

3. 遍历子图获取所有最短路径
   在这个最短路径子图中，用**深度优先搜索(DFS)或广度优先搜索(BFS)**遍历所有从S到T的路径——这些路径就是全部的最短路径。遍历过程中注意标记已访问节点（避免无向图中回头走重复节点），记录每一条完整路径即可。

对比原思路的优势 #

• 效率更高：仅调用一次Dijkstra，后续在极小的子图中搜索，避免了重复运行Dijkstra的冗余计算。
• 结果准确：不会因为误删共享边而漏解，所有可能的最短路径都被包含在子图中，遍历即可全部找到。

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