我需要在图中找到从第一个顶点到最后一个顶点的每条路径中出现的最少边数。例如 - 在图像中，如果第一个顶点是 V0，最后一个顶点是 V8，那么从 V0 到 V8 的每条路径中出现的最少顶点数是 2，它们是绿色的（或代替 V6-V8可能是 V0-V3 或 V3-V6）。
示例图片：
已经搜索了一段时间，但找不到（或想到）任何算法来做到这一点......
问问题
654 次
1 回答
0
您的问题相当于在图中找到最小 st 割，因为该割给出了最小的边集，如果删除，则断开 s 和 t。这与说每条路径都经过最小切割中的某个边缘相同。
有许多算法可以找到最小 st 割。例如，最大流最小割定理指出，从 s 到 t 的最大流的值（如果每个边都有单位容量）与最小 st 割中的边数具有相同的流。因此，任何最大流算法，例如 Ford-Fulkerson 或 Edmonds-Karp，都可以用于直接计算最小切割的成本。从那里，通过在残差图中找到从 s 可到达的所有边并获取在该集合中具有一个端点并且在补集中具有另一个端点的所有边，很容易恢复最小切割。
希望这可以帮助！
于 2013-01-22T08:07:48.407 回答