algorithm - 在具有约束的图中找到顶点不相交路径的最大数量

Question

给定一个无向图 G=(V,E)，每条边都与一个非负值相关联。

如何在图 G 上找到从 s 到 t 的最大顶点不相交路径数，并限制路径长度之和不大于预定义值 T。

Answer 1

您可以从将顶点不相交路径问题转换为边不相交路径问题开始。参见 this answer to other question了解详情。

现在你可以解决Minimum-cost flow problem在此图上找到任意数量的具有最小路径长度总和的不相交路径。这样做，为每条边分配等于 1 的流量，然后在 s 和 t 之间搜索流量等于所需路径数的最小成本流。

要找到最大路径数，对二分搜索的每个步骤应用最小成本流过程，从一些初始路径数开始，这可能由以下过程之一确定:

1. 如果你预计路径的最大数量很大，解决Maximum flow problem对于这张图。
2. 如果您希望路径的最大数量较小，请使用单边二分搜索(也使用每一步的最小成本流过程)。