如何在 DAG 中找到一组覆盖从源到汇的所有边的路径？

Question

我有一个有向无环图（由邻接矩阵给出）、一个源节点和一个汇节点。我想找到一组路径 P 的基数不超过边的数量，从源到汇，这样对于图中的每个边 e，存在路径 p 在 P 这样的 e 在 p.

我的想法是找到图中的所有路径，一旦覆盖所有边我就停止。我认为这个想法不是最好的，可能还有更好的方法。

我从开始：

def all_paths(adjm, source, sink, path, edges):
    # def covered(E, P):
    #     e = []
    #     for p in P:
    #         e.extend([(p[i], p[i + 1]) for i in range(len(p) - 1)])
    #     if set(e) == set(E):
    #         return True
    #     else:
    #         return False

    path = path + [source]

    if source == sink:
        return [path]

    paths = []
    for child in range(source + 1, adjm.shape[0]):  # I assume that the nodes are ordered
        if adjm[source, child] == 1:
            if child not in path:
                # if not covered(edges, paths):
                paths.extend(all_paths(adjm, child, sink, path, edges))

    return paths

Answer 1

"a set of paths P of cardinality no more than the number of edges"

好吧，如果允许每条边一条路径，则有一个非常简单的算法可以工作：

• 使用 Dijkstra 算法预先计算从 source 到所有其他节点的路径。
• 使用 Dijkstra 算法预先计算从所有其他节点到 sink 的路径，但假设每条边都朝相反的方向移动。
• 将 P 初始化为空集。
• 对于图中的每条边 u-v：
  • 通过连接从 source 到 u 的预计算路径，然后是边 u-v，然后是从 v 到 [=11= 的预计算路径，形成一条路径].
  • 将此路径添加到 P。
• Return P.

结果集包含的路径使得每条边都包含在至少一个路径中，通过构造。

您还可以很容易地改进算法，方法是维护到目前为止使用的一组边，在将路径添加到 P 时更新这组边，并在循环中跳过 u-v 如果已经在集合中了。