基于预计算最短路径边，能否更高效生成DAG中全部最短路径？

能借助这个先验知识显著提升效率，核心原因是这个子DAG中所有从起点到终点的路径必然是最短路径，完全不需要再处理非最短路径的分支或校验，具体优化方向包括：

• 省略距离校验步骤：常规的最短路径枚举函数会在遍历过程中反复验证路径长度是否等于预计算的最短距离，而这个子DAG里的路径天生满足最短距离要求，直接跳过这部分校验能节省大量计算开销。
• 基于拓扑排序的高效路径生成：利用DAG的拓扑序特性，从起点开始按拓扑顺序逐层拼接路径——子DAG中的每条边都符合最短路径的距离约束（即起点到u的距离 + 边u→v权重 = 起点到v的距离），所以沿着拓扑序扩展时，每一步都是在构建合法的最短路径，无需回溯或剪枝无效分支。
• 简化路径生成逻辑：常规函数需要大量分支剪枝逻辑来过滤非最短路径边，而这个子DAG里所有边都是最短路径的组成部分，剪枝逻辑可以全部移除，只需通过前驱节点的路径集合直接拼接生成当前节点的路径集合。
• 更低的时间与内存复杂度：优化后的算法复杂度可接近O(V+E+P)（V为节点数，E为边数，P为最短路径总数），远低于常规函数在包含冗余边的图上的运行复杂度，因为后者需要处理大量无效分支的判断与回溯。

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