Самый длинный путь в DAG

Чтобы найти самый длинный путь в группе обеспечения доступности баз данных, я знаю 2 алгоритма: алгоритм 1: выполнить топологическую сортировку + использовать динамическое программирование с результатом ~ или ~ алгоритм 2: перечислить все пути в группе обеспечения доступности баз данных с использованием DFS, и записать самое длинное. Кажется, что перечисление всех путей с помощью DFS имеет лучшую сложность, чем алгоритм 1. Это правда?

Ответы на вопрос(3)

DFS не исследует все возможные пути, если ваш граф не является деревом или лесом, и вы начинаете с корней. Второй алгоритм, который я знаю, сводит на нет веса и находит кратчайший путь, но он несколько медленнее, чемТоп сортировки + алгоритм DP что вы перечислили как # 1.

Алгоритм: принимает DAG G. Каждая дуга содержит одну переменную E

for each node with no predecessor :
    for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
    for each of his leaving arcs, E=max(E(entering arcs))+1.

max_path - это самый высокий E в пределах ребер, когда все узлы были обработаны.

используя & quot; DFS & quot ;:

def enumerate_dag(g):

  def enumerate_r(n, paths, visited, a_path = []):
    a_path += [n]
    visited[n] = 1
    if not g[n]:
        paths += [list(a_path)]
    else:
        for nn in g[n]:
            enumerate_r(nn, paths, visited, list(a_path))

  paths, N = [], len(g)
  visited = np.zeros((N), dtype='int32')

  for root in range(N):
    if visited[root]: continue
    enumerate_r(root, paths, visited, [])

  return paths

ВАШ ОТВЕТ НА ВОПРОС