图中具有特定长度的顶点不相交路径
Vertex disjoint paths with specific length in graph
输入：无环有向图G，节点s&t，自然数k。
输出：如果从 s 到 t 至少有 两条 条顶点不相交路径且最大路径长度为 k，则为真。否则 - return false.
运行时间应该是多项式的。
我的想法是分配每条边的容量 = 1 并找到最大流量。如果最大流量 >= 2，则 return 为真。但是最大流搜索最短的增强路径，如果您需要 2 条或更多路径，这并不总是最佳解决方案。我觉得广度优先搜索或深度优先搜索可以提供帮助，但我不知道如何将它们放在一起。
有人有解决该问题的算法吗？
有一种 Suurballe 算法可以在最小长度的图中找到两条不相交的路径。它适用于 O (|E|+|V|*log|V|).
输入：无环有向图G，节点s&t，自然数k。
输出：如果从 s 到 t 至少有 两条 条顶点不相交路径且最大路径长度为 k，则为真。否则 - return false.
运行时间应该是多项式的。
我的想法是分配每条边的容量 = 1 并找到最大流量。如果最大流量 >= 2，则 return 为真。但是最大流搜索最短的增强路径，如果您需要 2 条或更多路径，这并不总是最佳解决方案。我觉得广度优先搜索或深度优先搜索可以提供帮助，但我不知道如何将它们放在一起。
有人有解决该问题的算法吗？
有一种 Suurballe 算法可以在最小长度的图中找到两条不相交的路径。它适用于 O (|E|+|V|*log|V|).