4

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

一个例子：
在下面的这个网络中，所有边的容量都是 1。不难看出 from sto的最大流量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

在此处输入图像描述

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

4

1 回答 1

0

根据您的评论，我假设所有弧都是定向的并且容量为 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并在列表中拼接弧线。另一方面，也许您的图表足够小，这无关紧要。

于 2019-01-08T16:14:57.600 回答