Как найти набор путей, охватывающих все ребра от источника до приемника в DAG?

Question

У меня есть направленный ациклический c граф (заданный матрицей смежности), узел источника и узел приемника. Я хотел бы найти набор путей 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

"набор путей P с количеством элементов не более, чем число ребер"

Что ж, если вам разрешен один путь на ребро, существует очень простой алгоритм, который работает :

• Предварительно вычислить пути от source до всех других узлов с использованием алгоритма Дейкстры.
• Предварительно вычислить пути от всех других узлов до sink с использованием алгоритма Дейкстры, но представив, что каждое ребро входит в обратное направление.
• Инициализируйте P как пустой набор.
• Для каждого ребра u-v в графе:
  • Сформируйте путь путем объединения предварительно вычисленного пути из source до u, затем ребро u-v, затем предварительно вычисленный путь от v до sink.
  • Добавьте этот путь к P.
• Return P.

Результирующий набор содержит пути, так что каждое ребро включено, по крайней мере, в один путь, по построению.

Вы также можете улучшить алгоритм довольно просто, поддерживая набор ребер, использовавшихся до сих пор, обновляя этот устанавливается при добавлении пути к P и пропуску u-v в l oop, если он уже есть в наборе.