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

Question

我明白 Ford-Fulkerson Algorithm可以找到一个流网络中可以从源(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

有人问了类似的问题here但似乎没有得到明确的答复。

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 的列表。输出需要后处理以去除非最大流。

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 使用邻接表表示，并在列表中和列表外拼接弧。另一方面，也许您的图表足够小以至于无关紧要。