理论基础：Dijkstra算法及其扩展目标
在图论与路线优化的研究中，扩展Dijkstra算法成为解决更丰富场景的关键工具。本节聚焦如何将经典的Dijkstra从单源最短距离计算扩展到查找图中所有最短路径的能力，以便在同一距离下给出全部可行路线的集合。本文的核心目标可以用一句话概括：扩展Dijkstra算法：从理论到代码的完整实现指南，查找图中所有最短路径。
回顾
在实际应用中，找到全部等长最短路径通常用于可解释性分析、备选路线选择以及鲁棒性评估。为了实现这一点，我们需要从dist数组出发，筛选出参与最短路径的边集合，进而构建一个只包含最短路径的有向无环图(DAG)，最后对该DAG进行路径枚举。通过这种方式，理论与实践相结合，实现对所有最短路线的完整覆盖。
Dijkstra算法回顾
第一阶段，使用优先队列维护当前已知的最短距离，确保每次扩展都沿着最短路来探索新节点。第二阶段，更新相邻边的距离并记录可能的前驱结构。此处保留的只是距离信息，后续步骤将利用距离信息来筛选边进入DAG。通过这种设计，可以保持对复杂图的可扩展性，同时为枚举提供精准的边集合。
第三阶段，建立一个仅包含最短路径边的DAG，其中(u→v)只有在 dist[u] + w(u,v) = dist[v] 时才存在。该结构天然有序且无环，方便后续的路径遍历。最后，从源点到目标点的所有最短路径便可以通过在DAG上执行DFS或DP枚举得到。通过这种分步设计，理论正确性与实现复杂度都得到清晰分离。
扩展到所有最短路径的核心思想
核心思想是：在得到源点到各顶点的最短距离dist之后，筛选出所有可能属于最短路径的边，构成一个最短路径DAG。随后在该DAG上进行路径枚举，能够完整地输出所有从源点到目标点、长度等于 dist[target] 的路径集合。此流程的关键点在于边的筛选条件和有向无环特性的保持，以及枚举过程的剪枝策略。对于含有大量等长最短路径的图，枚举结果可能呈指数级增长，因此实现中往往需要考虑性能与可控输出的权衡。
从单源最短路径到所有最短路径的扩展思路
在传统Dijkstra的框架下，目标是得到从源点到各顶点的最短距离，及其一个可选的最短路径。本文的扩展思路在于利用距离信息，建立最短路径DAG，并在此基础上进行全量枚举，得到所有长度等于最短距离的路径。这一步骤提供了从单一解到多解的转换能力，适用于需要备选方案的应用场景。
边缘筛选的原则是：若图中存在一条有向边(u,v)且 dist[u] + w(u,v) = dist[v]，那么这条边就可能属于某条从源点出发的最短路径，我们将在DAG中保留它。反之，如果该边不满足上述关系，则它不能出现在任何以最短距离为目标的路径中。通过这个原则，我们将原图转换为一个仅包含最短路径边的结构。
路径枚举的策略通常是对DAG进行深度优先搜索(DFS)或动态规划（DP）式的组合，逐步从源点沿着DAG走向目标点，收集所有可行的路径序列。这一过程天然具有并行化的潜力，但也会因为结果数量的指数级增长而带来时间与内存的压力，因此在实际应用中需要对结果进行合理的控制和输出分步化处理。
实现步骤：从距离计算到最短路径DAG构建
步骤概览
实现过程可以分为四个阶段：1）构建图与初始Dijkstra计算，2）记录dist数组，3）基于dist筛选边构建DAG，4）从源点到目标点的所有最短路径枚举。每个阶段都要保持数据结构的清晰性，以便后续的调试与性能优化。
Dijkstra的正确性保证来自于对非负权边的依赖，以及在松弛过程中对dist的严格更新。距离信息一旦稳定，边的筛选就能可靠地构成最短路径DAG。
枚举的输出限制在设计阶段需要明确：是否需要输出所有路径、是否需要按字典序排序、以及是否需要懒加载式输出以降低峰值内存消耗。以上决策都会直接影响实现细节与接口设计。
DAG的性质与正确性保证
DAG性质确保不存在环路，因 dist[v] 总是严格大于 dist[u]（在边权为正的前提下），或在平行边情况下仍保持单向增量关系。正确性保证来自于：任意一条从s到t的最短路径都在DAG中存在一个对应的有向路径，而反之，DAG中的任意从s到t的路径都具有长度等于 dist[t]。因此，枚举DAG中的所有s→t路径即可得到全部最短路径。
复杂度考量：Dijkstra阶段的时间复杂度通常为O((n + m) log n)，而DAG的边数在最坏情况下接近原图边数，但通常远小于完整图。枚举阶段在结果数量较大时会成为瓶颈，因此应结合具体应用场景设计输出策略。
代码实现：从Dijkstra到遍历所有最短路径
核心数据结构
为实现可读性与性能并重的解决方案，推荐使用以下数据结构：图的邻接表表示、dist数组用于记录最短距离、dag字典/列表存储最短路边集合，以及一个用于路径枚举的回溯栈。同时，使用优先队列实现Dijkstra以保持对大规模图的高效性。
另外，为了便于演示与测试，可以用简单的整型或字符串节点标识，并提供一个可复用的桥接函数来构造
详细实现步骤
实现的关键步骤如下：1）初始化数据结构；2）执行Dijkstra获得dist；3）遍历所有边，筛选出属于最短路径的边，构建DAG；4）在DAG上进行DFS枚举从源点到目标点的所有路径。下面给出一个简洁而完整的Python实现，包含注释以便理解各步的作用。
import heapq
from collections import defaultdictdef dijkstra(graph, s):# graph: dict {u: [(v, w), ...], ...}dist = {u: float('inf') for u in graph}dist[s] = 0pq = [(0, s)]while pq:d, u = heapq.heappop(pq)if d != dist[u]:continuefor v, w in graph[u]:nd = d + wif nd < dist[v]:dist[v] = ndheapq.heappush(pq, (nd, v))return distdef build_shortest_path_dag(graph, dist):# Returns DAG as adjacency list: dag[u] -> [v, ...]dag = defaultdict(list)for u in graph:for v, w in graph[u]:if dist.get(u, float('inf')) + w == dist.get(v, float('inf')):dag[u].append(v)return dagdef enumerate_all_shortest_paths(dag, s, t):# DFS on DAG to collect all paths from s to tpaths = []path = []def dfs(u):path.append(u)if u == t:paths.append(list(path))else:for v in dag.get(u, []):dfs(v)path.pop()dfs(s)return paths# Example usage
# Graph:
# 0 -> 1 (weight 1), 0 -> 2 (weight 1)
# 1 -> 3 (weight 1)
# 2 -> 3 (weight 1)
# 3 -> 4 (weight 1)
graph = {0: [(1, 1), (2, 1)],1: [(3, 1)],2: [(3, 1)],3: [(4, 1)],4: []
}
s, t = 0, 4dist = dijkstra(graph, s)
dag = build_shortest_path_dag(graph, dist)
all_paths = enumerate_all_shortest_paths(dag, s, t)print("Shortest distances:", dist)
print("All shortest paths (by node sequence):")
for p in all_paths:print(p)
数据输入示例中，节点可用整数或字符串表示，边权为非负数。上述实现中，dist记录每个节点到源点的最短距离，dag保存所有可能的最短路径边，最后通过DFS枚举得到从源点到目标点的所有路径序列。
如果目标是输出路径的边集合而非顶点序列，可以在输出阶段将路径转换为边的列表，或直接在DFS中输出边序列。对于大规模图，建议实现带限流的输出策略，例如按需生成、分页输出或将结果写入外部存储。
性能分析与边界情况
时间复杂度与空间复杂度
在最常见的实现中，Dijkstra阶段的时间复杂度为O((n + m) log n)，其中n为顶点数、m为边数。构建DAG的时间复杂度为O(m)，因为需要检查每条边的条件。枚举所有最短路径的时间复杂度与输出的路径数量成正比，最坏情形可能达到指数级，空间复杂度受输出规模影响。总体而言，在中等规模图上，该实现可以在合理时间内完成全量枚举。
对于极端情况，例如同一距离有大量互相独立的最短路径，必须对输出做控制。常用策略包括：限制最大输出条数、仅输出前K条最短路径、或采用逐步输出的懒加载模型。
若边权非负且图结构较难构建完整的DAG，亦可采用剪枝策略，在DFS时优先选择通过更多的高概率边的路径，以提升平均性能。
实际应用中的注意事项
在实际工程中，数据规模与内存约束决定了是否需要并行化枚举或分阶段输出。数据结构设计要尽量简洁，避免重复存储，尤其是在保存所有路径时。并且，测试阶段应包含具有多条等长最短路径的图，以验证边筛选与枚举逻辑的正确性。
为了便于维护，推荐将Dijkstra、DAG构建、以及路径枚举分成独立的模块，并提供清晰的API接口，便于在不同图数据和需求场景下进行二次开发。
