graph-theory - 计算对向环上的发散路径

Question

我需要在下图中计算从 A 到 B 的两条路径，约束条件是路径不能共享任何边：

嗯，好的，不能发图片，这是一个链接。

所有边都有正权重；对于这个例子，我认为我们可以假设它们是平等的。我天真的方法是使用 Djikstra 的算法来计算第一条路径，如上图的第二张图所示。

然后我从图中删除边并尝试计算第二条路径，但它失败了。是否有 Djikstra、Bellman-Ford（或其他任何东西）的变体可以计算上面第三张图中显示的路径？（没有特殊知识和删除对向链接，就是我的意思）

Answer 1

您正在寻找的是边缘不相交的路径。门格尔定理将为您提供最大数量的边缘不相交路径。要找到最短对，请查看Edge disjoint shortest pair algorithm：

1. 对给定的顶点对运行最短对算法
2. 将最短路径的每条边（相当于两个相反方向的弧）替换为指向源顶点的单个弧
3. 使上述每个弧的长度为负
4. 运行最短路径算法（注意：算法应该接受负成本）
5. 擦除找到的两条路径的重叠边缘，并反转第一条最短路径上剩余弧的方向，使其上的每个弧现在都指向汇顶点。结果是所需的一对路径。