Warum können wir nicht die kürzesten Wege mit negativen Gewichten finden, indem wir einfach eine Konstante hinzufügen, sodass alle Gewichte positiv sind?

Ich lese gerade eine Einführung in Algorithmen und komme von Johnsons Algorithmus, der davon abhängt, ob alle Pfade positiv sind.

Das Algo hängt davon ab, eine neue Gewichtsfunktion (w ') zu finden, die für alle Kanten positiv ist und die Richtigkeit der Beziehungen der kürzesten Wege beibehält.

Dazu werden die Werte für h (s) und h (d) berechnet, die zum ursprünglichen Wert von w addiert werden sollen.

Meine Frage ist, warum nicht einfach das kleinste w im Diagramm finden und an allen Kanten hinzufügen? Dies erfüllt beide Bedingungen und erfordert weniger Berechnung.

algorithms graph-theory graphs shortest-path Mr.Me
quelle

Haben Sie versucht, Ihren Anspruch zu beweisen oder ein Gegenbeispiel zu finden? Hinweis: Ihre Intuition ist falsch. (Community, ich bin mir ziemlich sicher, dass dies ein Duplikat ist. Kannst du es finden?)

Raphael

@ Raphael Ich bin mir ziemlich sicher, dass es auch ein Betrüger ist, aber ich dachte, es wäre schneller, darauf zu antworten, als den Betrüger zu finden.

David Richerby

@Raphael Es tut mir leid, da ich meine Frage nicht in einem bestimmten Format formulieren konnte und nicht danach suchen konnte.

Mr.Me

Wir haben eine Frage, die dies bereits erklärt , aber sie wurde als Dup einer anderen Frage markiert , die ziemlich verwirrend und schwer zu verstehen ist und mehrere verschiedene Fragen miteinander vermischt . Daher denke ich, dass diese Frage einen Wert gegenüber dem hat, was wir vorher hatten. Wenn Sie wollten, könnten wir die Dups vermutlich neu ausrichten (schließen Sie sie als Dup davon, anstatt von dem, worauf sie aktuell zeigen).

Antworten:

Durch Hinzufügen einer Gewichtung zu jeder Kante werden lange Pfade stärker gewichtet als kurze Pfade. (Lang im Sinne vieler Kanten.)

$-2$ $a$ $b$ $3$ $1$ $2$ $5$ $6$

David Richerby
quelle

Das Erhöhen jedes Kantengewichts um den gleichen Betrag erhöht nicht notwendigerweise jeden Pfad um den gleichen Abstand. Vielmehr ist die Zunahme der Pfade oft unverhältnismäßig, was davon abhängt, wie viele Kanten der Pfad hat.

Pendechosen
quelle

Dieser Effekt wird bereits in der anderen Antwort erwähnt.

Yuval Filmus

Ich habe es nur bis zur Verwirrung umformuliert.

Pendechosen