扩展Dijkstra算法：查找并打印所有最短路径

本文详细阐述了如何修改标准dijkstra算法，使其不仅能找到一条最短路径，还能在存在多条等长最短路径时，识别并打印所有这些路径。核心在于调整距离更新条件，并利用集合存储每个节点的多个父节点，进而通过递归方式重构所有等效最短路径。

Dijkstra算法多最短路径查找与实现

Dijkstra算法是解决单源最短路径问题的经典算法。然而，其标准实现通常只记录并输出一条最短路径，即使图中存在多条具有相同最短距离的路径。在某些应用场景中，我们可能需要获取所有这些等效的最短路径。本文将指导您如何对Dijkstra算法进行改造，以实现这一功能。

核心修改点

要让Dijkstra算法能够识别并记录所有最短路径，我们需要对两个关键部分进行修改：距离更新的条件判断和父节点（前驱节点）的存储方式。

1. 距离更新条件调整

标准Dijkstra算法在更新节点距离时，通常使用严格小于的条件来判断是否找到了一条更短的路径。为了捕获等长的最短路径，我们需要将这个条件放宽为小于或等于。

• 原始条件： 当 `shortest_distance + edge_distance
• 修改后条件： 当 `shortest_distance + edge_distance

这个修改是基础，它允许算法在发现一条与当前最短路径等长的路径时，依然进入更新逻辑。

2. 父节点集合管理

由于一个节点可能通过多个不同的前驱节点到达，且这些前驱节点形成的路径都具有相同的最短长度，因此我们需要将每个节点的父节点存储为一个集合（例如数组），而非单个值。

在修改后的距离更新逻辑中，根据新路径的长度与当前记录的最短距离的关系，我们需要区分两种情况：

标签： edge