Längster Pfad

Die Aufgabe, den einfachen Weg maximaler Länge in einem gegebenen Graphen zu finden, bezeichnet man in der Graphentheorie und der theoretischen Informatik als longest path problem (englisch für Problem des längsten Weges). Ein Weg heißt einfach, wenn er keinen Knoten mehrfach enthält. Die Länge des Weges kann auf zwei Arten gemessen werden: entweder durch die Anzahl der Kanten oder (in einem gewichteten Graphen) durch die Summe der Gewichte seiner Kanten. Im Gegensatz zum Problem des kürzesten Weges, welches sich in polynomieller Laufzeit lösen lässt, gehört das Problem des längsten Weges zu der Gruppe der NP-schweren Probleme. Dies bedeutet, dass es sich nicht in polynomieller Laufzeit lösen lässt, außer wenn P=NP wäre. Es kann gezeigt werden, dass auch eine Approximation schwierig ist.Das Problem kann jedoch für gerichtete, nicht-zyklische Graphen mithilfe einer topologischen Sortierung in linearer Zeit gelöst werden. Ein wichtiges Anwendungsgebiet ist das Finden des kritischen Weges in Planungsaufgaben.