Finden Sie den längsten Pfad in einem gerichteten zyklischen Diagramm von einer Quelle S zu einem Ziel f. Angenommen, es gibt keine positiven Gewichtszyklen

Question

Ich muss den längsten Pfad in einem gerichteten zyklischen Diagramm von einer Quelle S zu einem Ziel f finden. Angenommen, keine positiven Gewichtszyklen existieren, obwohl keine positiven Gewichtszyklen vorhanden sind, gibt es Zyklen von 0 oder negativen Gewichten. Kann jemand einen Algorithmus vorschlagen, um in diesem Fall den längsten Weg zu finden? Bitte zitieren Sie nach Möglichkeit Quelle.

Danke

Answer 1

Ich bin mir nicht sicher, ob dies funktioniert (muss es überprüfen), aber ... Sie können etwas Ähnliches tun:

Lassen min = min weight on the graph.
max = max weight on the graph.
Setzen Sie neue Gewichte für alle Kanten = wNew(e) = max - (wOld(e)-min).

Jetzt gibt es negative Wights und die Gewichte sind in umgekehrter Reihenfolge (dh wenn w(e1) war größer als w(e2) es ist jetzt kleiner).

Was ist, wenn wir jetzt nach dem kürzesten Weg suchen?

Answer 2

Negieren Sie einfach Ihre Kantengewichte und führen Sie einen kürzesten Pfadalgorithmus (z. B. Bellman-Ford).

Zyklen mit Nullgewicht könnten ein Problem sein. Sie müssen die Krawatten auf Ihren Wegen brechen, indem Sie das kürzeste (in Länge, nicht in Gewicht) auswählen. Eine Möglichkeit, dies zu tun, besteht darin, Ihre Gewichte ein Paar (-(Originalgewicht), 1) zu machen, sie paarweise hinzuzufügen und lexikografische Ordnung zu machen.

Siehe auch Längster Weg zwischen zwei Scheitelpunkten

Answer 3

Wenn Sie ein DCG haben, können Sie für immer für immer schaufeln, bevor Sie zu Ihrem Ziel kommen, das wäre der "längste Weg". In diesem Fall ist die Frage unvollständig, und der Algorithmus sieht wahrscheinlich je nach Einzelheiten unterschiedlich aus.

Das klingt nach Hausaufgaben.