Wie den kritischen Pfad eines gerichteten azyklischen Graphen berechnen?

Question

Was ist der beste (in Bezug auf die Leistung) Art und Weise den kritischen Pfad eines gerichteten azyklischen Graphen zu berechnen, wenn die Knoten des Graphen Gewicht haben?

Zum Beispiel, wenn ich die folgende Struktur:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

Der kritische Pfad sollte A-> B-> F (Gesamtgewicht: 10)

Answer 1

Ich habe keine Ahnung über „kritische Pfade“, aber ich nehme an, Sie meinen dieser .

Das Finden des längsten Pfades in einem azyklischen Graphen mit Gewichten ist nur möglich durch den ganzen Baum durchquert und dann die Längen zu vergleichen, da man nie wirklich wissen, wie der Rest des Baumes gewichtet wird. Sie können mehr über Baumdurchlauf finden Sie unter Wikipedia . Ich schlage vor, Sie gehen mit Pre-Order Traversal, da es einfach und einfach umsetzbar.

Wenn Sie häufig abzufragen gehen, möchten Sie vielleicht auch die Kanten zwischen den Knoten mit Informationen über das Gewicht ihrer Unterbäume beim Einführen erweitern. Dies ist relativ billig, während wiederholt Traversal kann extrem teuer sein.

Aber es gibt nichts, um wirklich Sie von einer vollständigen Traversal zu sparen, wenn Sie es nicht tun. Die Reihenfolge spielt keine Rolle, solange Sie tun eine Traversal und nie zweimal den gleichen Weg gehen.

Answer 2

Ich würde dies mit dynamischer Programmierung lösen. Um die maximal Kosten von S bis T zu finden:

• sortieren Topologisch die Knoten des Graphen als S = x_0, x_1, ..., x_n = T. (Ignorieren Sie alle Knoten, die S erreichen kann oder von T zu erreichen.)
• Die Kosten von S bis S ist das Gewicht von S.
• Angenommen, Sie die maximal Kosten von S berechnet haben für alle X_i i

Answer 3

Es ist ein Papier, das einen Algorithmus dafür haben vorgibt: „Kritischer Pfad in einem Aktivitäts Netzwerk mit Zeitdruck“. Leider konnte ich nicht einen Link auf eine kostenlose Kopie finden. Kurz davon, kann ich nur die Idee der Modifizierung http://en.wikipedia.org/ wiki / Dijkstra% 27s_algorithm oder http://en.wikipedia.org/wiki/A *

UPDATE: Ich entschuldige mich für den crappy Formatierung-serverseitigen Abschlag Motor scheinbar gebrochen

.

Answer 4

Meine erste Antwort so entschuldigen Sie bitte für jedes Nicht-Standard, was von der Kultur der Stackoverflow.

Ich denke, die Lösung ist einfach. Nur die Gewichte negieren und den klassischen kürzesten Weg für DAG (modifiziert für Gewichte von Eckpunkten natürlich) laufen. Es sollte ziemlich schnell laufen. (Zeitkomplexität von O (V + E) vielleicht)

ich denke, es sollte funktionieren, wenn Sie die Gewichte negieren werden, die größte kleinste worden, zweitgrößte zweiter sein wird, kleinste und so weiter, als ob a > b dann -a < -b. Dann DAG ausgeführt wird, sollte ausreichen, da sie die Lösung für den kleinsten Pfad des negierten einen finden und somit längsten Weg für das Original zu finden

Answer 5

Versuchen Sie, die A * Methode.

A * -Algorithmus

Am Ende mit den Blättern zu beschäftigen, nur alle von ihnen führen auf einen letzten Punkt als Ziel gesetzt.