在未知大小的加权有向图上，如何迭代两个顶点之间从最短到最长的所有可能的非循环路径？

Question

我们可以假设所有边权重都是正数，并且可以枚举从顶点向外引出的边，以及在O（1）时间内向内引导的边。例如，您可以执行Dijkstra遍历（或带有可容许启发式的A *），并标记每个顶点的距离，直到您找到结束顶点，然后在它们描述可能的前辈时反转这些标记在最佳路径上。也就是说，对于每个可能的前驱，如果标记的距离之间的差等于连接它们的边的权重，则可以确定它是否在贪婪的最优路径上找到。

当考虑可能的前辈时，进入边的成本加上到每个顶点的最优距离之间的差值等于将该边包含在解中导致的最优性损失（最优路径上的边为零）。所以也许这个问题变成：如何才能最大限度地延长产量全部可能的路径按优化程度递减排列？是否有一种干净的方式来执行这种元图的最佳优先遍历？

这似乎是一个有用的解决方案的正确方向。也许是为了记住一个有用的事情是，如果到目前为止，你已经探索路径的一部分可能是一个解决方案的一部分是由至少X欠佳，检查周期只需要沿最后X完成访问距离（x次优的任何路径不可能包含比x更长的周期）。

有没有更高效的方法？

作为一个奖励问题，是否也可以在具有负边权重的图形上（已知大小）执行此操作？如果引入负循环，它会变得更加困难吗？ （请记住，因为我们只查找非循环路径，所以这并不一定意味着最佳解决方案会失控。）

Answer 1

Credit to n.m .:关于K-shortest-path routing的维基百科文章描述了各种现代化的方法，包括用于Dijkstra泛化的伪代码，以及链接到2011年关于K *的论文，该论文也利用启发式。

Answer 2

对于N个节点的完整图，存在（N-2）个数量级！可能从节点A到节点B进行非循环连接。考虑它......这应该是巨大的数字，如果你只需要K（足够大，但是合理的数量）修改，你最好在评论中提到K-shortest_path。

如果你可以管理足够的内存来保存所有可能的方法，那么有一个明显的解决方案 - 生成所有可能的方法并按重量对它们进行分类。如果没有，您必须将答案转储到磁盘然后收集它们。

您可以使用修改的BFS枚举所有可能的方法 - “visited”数组传递给递归调用，而不是全局布尔数组。当您访问目的地时，将其添加到全球解决方案地图（关键 - 权重，价值列表）。

如果您无法承担在内存中保留所有路径，则可以将它们转储为节奏文件。天真的解决方案：打开名称为0的软件，最多填充10个数字 - 或任何符合您需要的内容 - 重量，并为路径添加一行。收集所有程序后，按适当的顺序读取文件并形成最终结果。

注意如果可以，最好不要打开/追加/关闭文件。例如，您可以在地图上收集路径，并在路径总数超过某个限制时仅转储最长列表。