计算对向环上的发散路径

Question

我需要计算下图中从 A 到 B 的两条路径，限制路径不能共享任何边：

嗯，好吧，不能发布图像，这里有一个 链接。

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

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

Answer 1

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

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