Längster Pfad in einem DAG - Algorithmus, Graph, gerichtete azyklische Graphen

Um den längsten Pfad in einer DAG zu finden, ist mir 2 bekanntAlgorithmen: Algo 1: eine topologische Sortierung durchführen + dynamische Programmierung auf das Ergebnis der Sortierung anwenden ~ oder ~ Algo 2: alle Pfade in der DAG mit DFS aufzählen und die längste aufzeichnen. Es sieht so aus, als hätte die Aufzählung aller Pfade mit DFS eine bessere Komplexität als Algo 1. Stimmt das?

Antworten:

Ihre zweite Option ist falsch: DFS untersucht nicht alle möglichen Pfade, es sei denn, Ihr Diagramm ist ein Baum oder eine Gesamtstruktur und Sie beginnen mit den Wurzeln. Der zweite Algorithmus, den ich kenne, negiert die Gewichte und findet den kürzesten Weg, aber er ist etwas langsamer als der Top-Sortierung + DP-Algorithmus dass du als # 1 aufgelistet hast.

Zählen Sie alle Pfade in einer DAG mit "DFS" auf:

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

Kein DFS benötigt. Algorithmus: nimmt eine DAG G. Jeder Bogen enthält eine Variable 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 ist das höchste E innerhalb der Kanten, wenn alle Knoten bearbeitet wurden.