Dijkstra最短路径算法中多条最短路径的打印方案问询

你的思路完全可行——给每个节点维护多个父节点，而非单个父节点，是捕获所有最短路径的核心方法。下面直接说明如何修改原代码实现该功能：

1. 调整父节点存储结构 #

原代码用单个数组（如parent[]）存储每个节点的唯一父节点，现在要改为数组嵌套列表的形式，比如C++中用vector<vector<int>> parent(V)（V为节点总数），让每个节点能保存所有可产生最短路径的前驱节点。

2. 修改松弛操作逻辑 #

在Dijkstra算法的松弛步骤中，原逻辑仅更新最短距离和单个父节点，现在要分两种情况处理：

• 当dist[v] > dist[u] + weight(u,v)时：
  • 更新dist[v]为dist[u] + weight(u,v)
  • 清空parent[v]，再将u加入parent[v]（这是新的最短路径前驱）
• 当dist[v] == dist[u] + weight(u,v)时：
  • 直接将u加入parent[v]（找到另一条最短路径的前驱）

3. 递归回溯生成所有路径 #

原代码仅递归回溯单个父节点生成路径，现在要修改递归逻辑，遍历所有父节点来生成完整路径集合：

// 存储所有最短路径的列表
vector<vector<int>> allPaths;

// 递归回溯函数
void getAllPaths(int current, int start, vector<int>& path) {
    path.push_back(current);
    if (current == start) {
        // 反转路径，得到从起点到终点的顺序
        vector<int> reversedPath(path.rbegin(), path.rend());
        allPaths.push_back(reversedPath);
    } else {
        // 遍历当前节点的所有父节点，递归生成路径
        for (int p : parent[current]) {
            getAllPaths(p, start, path);
        }
    }
    path.pop_back(); // 回溯，移除当前节点以尝试其他父节点路径
}

// 调用示例（假设起点为0，终点为target）
vector<int> tempPath;
getAllPaths(target, 0, tempPath);

4. 打印所有最短路径 #

最后遍历allPaths列表，逐个输出每条路径即可。

这种修改方式完全能实现你的需求，核心就是通过多父节点存储所有可能的最短路径前驱，再通过回溯遍历所有分支生成完整路径集合。

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