Längster Weg in einer DAG
Um den längsten Pfad in einer DAG zu finden, sind mir zwei Algorithmen bekannt: Algo 1: Eine topologische Sortierung durchführen + Dynamische Programmierung für das Ergebnis der Sortierung verwenden ~ oder ~ Algo 2: Alle Pfade in der DAG mit DFS auflisten. und am längsten aufnehmen. Die Aufzählung aller Pfade mit DFS scheint komplexer zu sein als mit Algo 1. Stimmt das?