在图论应用中，基础的Dijkstra算法仅能返回两个节点之间的一条最短路径，当业务需要获取所有长度相等的最短路径时，就需要对原算法进行适当扩展。扩展的核心思路是在计算最短距离的同时，维护每个节点的最短路径前驱集合，从而回溯得到所有符合条件的路径。
基础Dijkstra算法回顾
基础Dijkstra算法用于计算带权有向图或无向图中，从起点到所有其他节点的最短距离，核心逻辑是维护一个距离数组和一个已访问节点集合，每次从待处理节点中选择距离最小的节点进行松弛操作。基础实现仅记录最短距离，不存储路径信息，因此无法直接得到所有最短路径。
基础Dijkstra核心逻辑
基础算法的关键步骤如下：
- 初始化起点距离为0，其他节点距离为无穷大
- 每次选取未访问节点中距离最小的节点，标记为已访问
- 对该节点的所有邻接节点进行松弛，更新邻接节点的最短距离
- 重复上述步骤直到所有节点都被访问或起点到目标节点的距离已确定
扩展Dijkstra查找所有最短路径的思路
要获取所有最短路径，需要在基础算法的基础上增加两个核心维护项：
1. 维护最短距离数组
和基础算法一致，记录起点到每个节点的最短距离，用于判断新路径是否为最短路径。
2. 维护前驱节点集合
对于每个节点，不再只记录一个前驱节点，而是记录所有能到达该节点且路径长度等于最短距离的前驱节点。当松弛操作发现新的路径长度等于当前最短距离时，将对应的前驱节点加入集合；如果发现更短的路径，则清空原有前驱集合，加入新的前驱节点。
3. 回溯生成所有路径
得到目标节点的最短距离和前驱集合后，通过深度优先回溯的方式，从目标节点向前遍历所有前驱节点，直到回溯到起点，即可得到所有最短路径。
代码实现示例
以下是使用Python实现的扩展Dijkstra算法，用于查找从起点到终点的所有最短路径：
import heapq
from collections import defaultdict
def find_all_shortest_paths(graph, start, end):
# graph格式：{节点: {邻接节点: 权重}}
# 初始化距离字典，起点距离为0，其他为无穷大
dist = {node: float('inf') for node in graph}
dist[start] = 0
# 初始化前驱节点集合，每个节点的前驱是列表
prev = defaultdict(list)
# 优先队列，存储(距离, 节点)
pq = [(0, start)]
# 已访问节点集合
visited = set()
while pq:
current_dist, current_node = heapq.heappop(pq)
# 如果当前节点已访问，跳过
if current_node in visited:
continue
visited.add(current_node)
# 如果当前节点是终点，不需要再处理邻接节点
if current_node == end:
break
# 遍历邻接节点
for neighbor, weight in graph.get(current_node, {}).items():
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
# 发现更短路径，更新距离，清空前驱集合
dist[neighbor] = new_dist
prev[neighbor] = [current_node]
heapq.heappush(pq, (new_dist, neighbor))
elif new_dist == dist[neighbor]:
# 发现等长最短路径，添加前驱节点
prev[neighbor].append(current_node)
# 回溯生成所有最短路径
all_paths = []
def backtrack(node, path):
if node == start:
# 到达起点，将路径反转后加入结果
all_paths.append(path[::-1])
return
for pre_node in prev[node]:
backtrack(pre_node, path + [pre_node])
if dist[end] != float('inf'):
backtrack(end, [end])
return all_paths, dist[end]
# 测试示例
if __name__ == '__main__':
# 定义测试图
test_graph = {
'A': {'B': 1, 'C': 2},
'B': {'D': 3, 'E': 2},
'C': {'D': 1, 'E': 3},
'D': {'E': 1, 'F': 2},
'E': {'F': 1},
'F': {}
}
paths, min_dist = find_all_shortest_paths(test_graph, 'A', 'F')
print(f"最短距离：{min_dist}")
print("所有最短路径：")
for p in paths:
print(' -> '.join(p))
算法复杂度分析
扩展后的算法时间复杂度相比基础Dijkstra算法有所增加：
- 时间复杂度：基础Dijkstra的时间复杂度为O((V+E)logV)，其中V是节点数，E是边数。扩展后需要维护前驱集合，最坏情况下每个节点的前驱集合可能包含所有其他节点，回溯生成路径的时间复杂度为O(V!)，但实际场景中通常不会出现这种极端情况，整体时间复杂度仍和基础算法同阶，仅常数系数增大。
- 空间复杂度：需要额外存储每个节点的前驱集合，最坏情况下空间复杂度为O(V²)。
适用场景说明
扩展后的Dijkstra算法适用于需要获取所有最短路径的场景，比如地图导航中需要给用户展示多条距离相同的最优路线、网络路由中需要选择多条等价最短路径做负载均衡等。如果只需要一条最短路径，使用基础Dijkstra算法即可，避免不必要的性能开销。
Dijkstra算法最短路径图论路径查找修改时间：2026-07-18 09:42:35