本文详细阐述了如何修改Dijkstra最短路径算法，使其能够识别并打印图中所有长度相等的最短路径，而不仅仅是单一路径。核心在于调整父节点追踪机制，当遇到多条路径长度相等的场景时，允许节点拥有多个父节点，并相应更新距离比较条件，以确保所有等长路径都能被记录和遍历。
标准的Dijkstra算法通常设计为找到从源节点到图中所有其他节点的一条最短路径。其核心在于维护一个 shortest_distances 数组记录最短距离，以及一个 parents 数组记录每个节点在最短路径树中的直接父节点。当算法在探索邻接节点时，如果发现一条严格更短的路径，它会更新 shortest_distances 并替换 parents 数组中对应的父节点。这种“严格更短”的条件以及“单一父节点”的存储方式，导致了当存在多条长度相同的最短路径时，标准Dijkstra算法只会记录并输出其中一条，而忽略其他等长路径。
为了解决这一问题，我们需要对算法进行两项关键修改：一是放宽距离更新条件，二是允许节点存储多个父节点。
要使Dijkstra算法能够识别所有最短路径，我们需要改变其处理父节点的方式。不再为每个节点存储一个单一父节点，而是存储一个父节点集合。当算法发现一条与当前已知最短路径长度相等的路径时，应将新的父节点添加到该集合中，而不是替换它。
具体来说，需要调整距离更新的判断条件，从严格小于 (
原始条件：
if edge_distance > 0 and shortest_distance + edge_distance < shortest_distances[vertex_index]:
应修改为：
if edge_distance > 0 and shortest_distance + edge_distance <= shortest_distances[vertex_index]:
这一改变允许算法在发现等长路径时也能进入更新逻辑。在此逻辑内部，我们需要区分两种情况来处理父节点集合：
如果 shortest_distance + edge_distance
如果 shortest_distance + edge_distance == shortest_distances[vertex_index]，这意味着我们找到了一条与当前已知最短路径长度相等的新路径。在这种情况下，我们不应清空父节点集合，而应将 nearestVertex 添加到 vertex_index 的父节点集合中。这确保了所有导致等长最短路径的父节点都被记录下来。shortest_distances[vertex_index] 保持不变，因为它已经是当前最短距离。
以下是一个基于JavaScript实现的Dijkstra算法修改示例，它允许跟踪并打印所有最短路径。
function dijkstra(adjacencyMatrix, startVertex) {
const nVertices = adjacencyMatrix[0].length;
// shortestDistances[i] 将保存从 startVertex 到 i 的最短距离
const shortestDistances = new Array(nVertices).fill(Number.MAX_SAFE_INTEGER);
// added[i] 为 true 表示顶点 i 已包含在最短路径树中
// 或从 startVertex 到 i 的最短距离已确定
const added = new Array(nVertices).fill(false);以上就是扩展Dijkstra算法以查找所有最短路径的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
126
收藏
