我需要在图中找到从第一个垂直点到最后一个垂直点的每条路径中出现的最少边数。例如-在图像中，如果第一个vertice是V0，最后一个vertice是V8，那么从V0到V8的每条路径中出现的最少顶点数是2，它们是绿色的（或者代替V6-V8的可能是V0-V3或V3-V6）。
示例图像：
已经搜索了一段时间，但找不到（或想不出）任何算法来执行此操作…
最佳答案
你的问题相当于在图中找到一个最小的s-t割，因为这个割给了最小的边集，如果去掉了它，就断开了s和t。这和说每条路径都经过最小割中的某条边是一样的。
求最小s-t割有很多算法例如，max-flow min-cut theorem表示从s到t的最大流值（如果每个边具有单位容量）与最小s-t切割中的边数具有相同的流。因此，任何最大流算法，如福特富尔克森或埃德蒙德卡普，都可以用来直接计算最小切割成本。从那里，很容易恢复最小割集，方法是从残差图中的s找到所有可到达的边，并取此集中有一个端点和补集中有另一个端点的所有边。
希望这有帮助！
关于algorithm - 每条路径中出现的边缘最少，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14453865/