在图中找到前K个路径的算法,没有公共顶点,负权重？

Question

我正在使用Bellman-Ford通过一些具有负权重的图表找到最短路径.该图不可能有循环,也没有双向连接.我想在图中找到K个最短路径,其中路径共享没有共同的节点.是否有算法我可以查看以了解如何执行此操作？简单的实现比目前的速度更重要.

补充:感谢您的评论.为了清楚起见,我正在寻找从指定的起始节点到指定的终端节点的最佳K方法,没有其他共同的节点.我需要全球最优; 顺序找到最佳和删除节点不会给出满意的结果.这个:https://en.wikipedia.org/wiki/Yen%27s_algorithm,给出了我所说的内容的味道,但在这种情况下,它需要非负边缘成本,它还允许共享节点.

Answer 1

我认为找到最小成本流可以解决这个问题。

让我们按以下方式转换图表：

1. 将除源节点和汇节点之外的每个节点v替换为通过从v1到v2的权重为 0 的边连接的两个节点v1 和v2。前一个v的入边进入v1 ，出边从v2离开。这样，问题就相当于不多次使用这些边。

2. 将所有边的容量设置为 1。

找到值K的流将为您提供K条不共享节点的路径（因为在这些新边中将容量设置为 1）。因此，如果该流是最小成本流，则这K条路径也具有最小可能的成本总和。

这是假设您没有直接连接源和接收器的边缘。单独检查该极端情况。