Wie finde ich den längsten Pfad in einer Grafik mit einer Reihe von Start- und Zielpunkten?

Question

Ich habe eine DAG (mit Kosten/Gewicht pro Kante) und möchte den längsten Pfad zwischen zwei Knotengruppen finden. Die beiden Gruppen von Start- und Zielknoten sind disjunkt und klein im Vergleich zur Gesamtzahl der Knoten im Diagramm.

Ich weiß, wie man dies effizient zwischen einen Start-und Zielknoten. Mit multiple kann ich alle Pfade von jedem Start bis zu jedem Zielknoten auflisten und den längsten auswählen - aber das erfordert eine quadratische Anzahl von Einzelpfad-Suchen. Gibt es einen besseren Weg?

Answer 1

Ich nehme an, dass Sie den längsten möglichen Pfad haben möchten, der in einem der Knoten aus dem ersten Satz beginnt und in einem der Knoten in dem zweiten Satz endet. Dann können Sie fügen zwei virtuelle Knoten:

• Der erste Knoten hat keine Vorgänger und seine Nachfolger sind die Knoten aus dem ersten Satz.

• Der zweite Knoten hat keine Nachfolger und seine Vorgänger sind die Knoten aus der zweiten Gruppe.

Alle neu hinzugefügten Kanten sollten kein Gewicht haben.

Die Grafik wäre immer noch eine DAG. Wenn Sie nun den Standardalgorithmus verwenden, um den längsten Pfad in der DAG zwischen den beiden neuen Knoten zu finden, erhalten Sie den längsten Pfad, der in der ersten Menge beginnt und in der zweiten Menge endet, außer dass eine zusätzliche Null- gewichtete Kante zu Beginn und eine extra Null gewichtete Kante am Ende.

Übrigens führt diese Lösung im Wesentlichen den Algorithmus von allen Knoten aus der ersten Menge aus, aber im Gegensatz zu dem sequenziellen Ansatz, den Ihre Frage vorschlägt.