在图中查找无公共顶点、负权重的前K条路径的算法是什么？

Question

在图中查找无公共顶点、负权重的前K条路径的算法是什么？

algorithmgraph-theoryshortest-pathbellman-ford

8

我正在使用Bellman-Ford算法找到带有负权重的图中的最短路径。该图不可能存在循环和双向连接。我想找到K个没有公共节点的最短路径。是否有算法可以帮助我学习如何做到这一点？目前简单的实现比速度更重要。

补充：感谢评论。为了清楚起见，我正在寻找从指定的起始节点到指定的结束节点的前K种方式，没有其他公共节点。我需要全局最优解；顺序查找最佳解并删除节点不能给出令人满意的结果。这个链接https://en.wikipedia.org/wiki/Yen%27s_algorithm 可以给出我所说的内容的大致思路，但在此情况下，它需要非负边缘成本，并且还允许共享节点。

- Mastiff

1

我猜图形可以假定为连通的，对吗？ - Codor

1

K最短路径是指没有共同节点的路径，例如连接两个顶点且仅共享这两个顶点的K最短路径。如果图形无环，则可以穷尽所有路径并选择最短的K条路径。 - opticaliqlusion

2

所以你有一个有向无环图？你现在做的是反复查找最短路径并删除内部节点，还是对全局优化感兴趣？ - David Eisenstat

1

当你说“前K种方式”时，你是指总和最小化还是第一种方式最小，然后是第二种方式...换句话说，对于K = 2，路径长度为-5，-1或-4，-3哪个更好？ - AlexAlvarez

1

目标是最小化成本总和。谢谢。 - Mastiff

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AlexAlvarez · Accepted Answer

我认为这个问题可以通过找到最小费用流来解决。

接下来按以下方式转换图：

1. 除源点和汇点外，将每个节点v替换为两个节点v1和v2，并在v1到v2之间连接一条权重为0的边。原先v的入边进入v1，出边从v2离开。通过这种方式，问题等价于不多次使用那些边。

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

找到一个值为K的流将给你K条不共享节点的路径（因为在新边上将容量设置为1）。因此，如果这个流是最小费用流，你将得到这些K条路径的最小可能成本总和。

前提是假设没有直接连接源点和汇点的边。请单独检查这种情况。