在图中查找前 K 路径的算法，没有公共(public)顶点，负权重？

Question

我正在使用 Bellman-Ford 寻找通过具有一些负权重的图形的最短路径。该图没有循环的可能性，也没有双向连接。我想找到图中的 K 条最短路径，其中路径不共享任何节点。有没有我可以查找的算法来学习如何做到这一点？目前，简单实现比速度更重要。

补充:感谢评论。明确地说，我正在寻找从指定起始节点到指定结束节点的前 K 种方法，没有其他共同节点。我需要一个全局最优；按顺序找到最佳节点并删除节点并不能给出令人满意的结果。这个:https://en.wikipedia.org/wiki/Yen%27s_algorithm , 给出了我正在谈论的内容的味道，但在这种情况下，它需要非负边成本并且它还允许共享节点。

Answer 1

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

让我们按以下方式转换图形:

1. 用两个节点 v1 替换除 source 和 sink 之外的每个节点 v和 v2 从 v1 到 v2 由权重为 0 的边连接。这前一个 v 的传入边进入 v1 和传出从 v2 离开。有了这个问题就等同于不使用这些边缘不止一次。

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

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

这是假设您没有直接连接源和汇的边。单独检查那个角落案例。