在最大流问题中，如何找到给出最大流的所有可能的路径集？

Question

据我了解，Ford-Fulkerson 算法可以找到流量网络中可以从源 ( s) 流向汇 ( )的最大流量。 但是是否有一种算法可以找到给出最大流量的所有可能的路径集？t

举个例子：
在下面的这个网络中，所有边的容量都是 1。不难看出，从s到 的最大流量t是 3。但是如何找到承载该流量的路径组合呢？

预期输出：
路径集 1：s-0-1-t, s-2-3-t, s-5-6-t
路径集 2：s-0-1-t, s-2-4-t, s-5-6-t
路径集 3：s-0-3-t, s-2-4-t, s-5-6-t
路径集 4：s-0-4-t, s-2-3-t, s-5-6-t

这里提出了类似的问题，但似乎没有得到明确的答案。

Answer 1

根据您的评论，我假设所有弧都是有向的且容量为 1。

高级伪代码是

define EnumerateFlows(G, s, t):
    if G has no s-t path:
        yield []  # solution with no paths
    else:
        for P in EnumeratePaths(G, s, t):
            derive G' = G - P
            let s-u be the first arc in P
            derive G'' = G' - {arcs s-v such that v < u}  # ensure canonically ordered solutions only
            for F in EnumerateFlows(G'', s, t):
                yield [P, F...]  # solution with P followed by the elements of F

yield其中函数的返回值是其主体中创建的所有 s 的列表。输出需要后处理以去除非最大流。

EnumeratePaths毫无疑问，Stack Overflow 上有一个解决方案，但为了完整起见，

define EnumeratePaths(G, s, t):
    if s = t:
        yield [s]
    else:
        for u in {successors of s in t}:
            for P in EnumeratePaths(G - {s-u}, u, t):
                yield [s, P...]

为了改进EnumerateFlows，值得添加检查以确保残差图中仍然存在最大流。

至于低级实现建议，我的建议是使用邻接列表表示形式，G并在列表中和列表外拼接弧。另一方面，也许你的图表足够小，所以这并不重要。