如何在图中找到所有不相交的顶点路径？

Question

假设在一张图中有3个目标节点。

顶点不相交的路径表示在路径中除了终点节点以外没有任何相同的节点。

对于任意一个单独节点，比如说节点 i，如何找到从节点 i 到这三个目标节点的所有顶点不相交的路径？

- datcn

---

请明确一下，您的意思是从“i”开始，经过每个目标节点，然后返回到“i”，没有重复，除了两端相同？另外，您想要找到所有这样的路径（如您所说）还是最短的路径（如标记所示）？ - Danica

在我的目的中，我想找到从节点i开始并以目标节点z结束的路径。如果有多条路径，则这些路径中除了节点i和节点z之外，不应该有相同的节点。我希望找到所有从i到z的路径。 - datcn

哦，这和我（以及 templatetypedef）理解的完全不同。所以你想要找到一组从 i 到 z 的路径，使得这些路径是不相交的？可能有许多这样的集合（取决于您选择哪条可能的路径）。所以也许您想做的是找到从 i 到 z 的所有路径（通过例如广度优先搜索），然后处理它们以找到一个不相交的集合。其中一种容易的方法，虽然不会找到最大的这样的集合或任何东西：选择一条路径从集合中，删除所有与该路径相交的其他路径，重复。 - Danica

当然，你可以结合我刚才描述的那个算法的两个步骤。也许先进行深度优先搜索，一旦找到一个有效的路径，就从图中删除所有它的节点并继续搜索。如果你指定想要某些特殊的不相交路径到达目标，那么肯定有更好的方法。(不过我仍然不知道你所说的有3个目标节点是什么意思...只是做这3次，还是找到从 i 到 x、y 和 z 的路径，使得 i->x、i->y 和 i->z 不相交?) - Danica

@Dougal，非常感谢。是的，你提出的深度优先然后删除它们的想法可能可以解决这个问题。至于3个目标节点在算法上实际上并没有太多业务。节点x和y与z相同，因此它只会重复查找到z的路径的过程。 - datcn

Answer 1

您可以通过将其转换为适当构建的图中的最大流问题来解决此问题。其思路如下：

1. 将图中的每个节点v拆分为两个节点：v_in和v_out。
2. 对于每个节点v，从v_in到v_out添加容量为1的边。
3. 用容量为1的u_out到v_in的边替换图中的每个其他边(u，v)。
4. 添加一个新的专用目标节点t。
5. 对于每个目标节点v，从v_in到t添加容量为1的边。
6. 从s_out到t找到最大流。流的值是节点不相交路径的数量。

这种构造背后的思想是这样的。从起始节点s到目标节点t的任何流路径必须具有容量为1，因为所有边缘都具有容量为1。由于所有容量都是整数，存在整数最大流。没有两条流路径可以通过相同的中间节点，因为在通过图中的节点时，流路径必须穿过从v_in到v_out的边缘，这里的容量已被限制为1。此外，该流路径必须通过结束于您已识别的三个特殊节点之一来到达t，然后沿着从该节点到t的边缘移动。因此，每条流路径都表示从源节点s到三个目标节点之一的节点不相交路径。因此，在此处计算最大流量对应于找到从s到任何三个目标之一的最大节点不相交路径的数量。

希望这可以帮助您！

- templatetypedef

---

也许我的“vertex-disjoint”表达不够清晰。对于节点s和节点t，存在一条路径s->a-〉b->c->d->t，还有另一条从s开始的路径，如s->e->f->g->h->t。在这种情况下，这是一条顶点不相交的路径。但如果存在一条路径，如s->e->f->g->d->t，则不是顶点不相交的路径。 - datcn

这个解决方案的运行时间是多少？O(nm)？ - razshan

@razshan 这样想一下：预处理花费了多少时间，最大流算法又花费了多少时间？ - templatetypedef

预处理看起来是线性时间，但从 s_out 到 to 找到最大流量将需要 O(n * m^2) 或 (n^2 * m)，这会影响大 Oh 符号。这个合理吗？ - razshan

步骤1和2，我们是否也需要将汇节点拆分为t_in和t_out？ - razshan