Johnsons Algorithmus

Johnsons Algorithmus ist ein Verfahren zur Bestimmung der kürzesten Wege zwischen allen Knotenpaaren in einem gerichteten Graphen mit Kantengewichten . Er erlaubt negative Kantengewichte , jedoch dürfen keine Zyklen mit negativen Gewichten existieren. Der Algorithmus verwendet den Bellman-Ford-Algorithmus , um eine Transformation des Eingabegraphen zu berechnen, die alle negativen Gewichte entfernt. Dadurch kann der Dijkstra-Algorithmus auf den transformierten Graphen angewendet werden. ^{[ 1 ] [ 2 ]} Benannt ist er nach Donald B. Johnson , der die Methode 1977 erstmals veröffentlichte. ^{[ 3 ]}

Eine ähnliche Neugewichtungstechnik wird auch in einer Version des Algorithmus für sukzessive kürzeste Wege für das Problem des minimalen Kostenflusses von Edmonds und Karp ^{[ 4 ]} sowie in Suurballes Algorithmus zum Finden zweier disjunkter Wege minimaler Gesamtlänge zwischen denselben zwei Knoten in einem Graphen mit nichtnegativen Kantengewichten verwendet. ^{[ 5 ]}

Der Johnson-Algorithmus besteht aus folgenden Schritten: ^{[ 1 ] [ 2 ]}

1. Zunächst wird dem Graphen ein neuer Knoten q hinzugefügt, der über Kanten mit dem Gewicht Null mit jedem der anderen Knoten verbunden ist.
2. Zweitens wird der Bellman-Ford-Algorithmus verwendet, ausgehend vom neuen Knoten q , um für jeden Knoten v das minimale Gewicht h ( v ) eines Pfades von q nach v zu finden . Falls in diesem Schritt ein negativer Zyklus entdeckt wird, wird der Algorithmus abgebrochen.
3. Anschließend werden die Kanten des ursprünglichen Graphen mithilfe der vom Bellman-Ford-Algorithmus berechneten Werte neu gewichtet: Eine Kante von u nach v mit der Länge ⁠ ⁠${\displaystyle w(u,v)}$ erhält die neue Länge w ( u , v ) + h ( u ) − h ( v ) .
4. Schließlich wird q entfernt, und der Dijkstra-Algorithmus wird verwendet, um die kürzesten Wege von jedem Knoten s zu jedem anderen Knoten im neu gewichteten Graphen zu finden. Die Distanz im ursprünglichen Graphen wird dann für jede Distanz D ( u , v ) berechnet, indem h ( v ) − h ( u ) zu der vom Dijkstra-Algorithmus zurückgegebenen Distanz addiert wird.

Die ersten drei Stufen von Johnsons Algorithmus sind in der folgenden Abbildung dargestellt.

Der Graph links in der Abbildung enthält zwei negative Kanten, aber keine negativen Zyklen. Der mittlere Graph zeigt den neuen Knoten q , einen mit dem Bellman-Ford-Algorithmus berechneten kürzesten Pfadbaum mit q als Startknoten sowie die an jedem anderen Knoten berechneten Werte h ( v ) als Länge des kürzesten Pfades von q zu diesem Knoten. Diese Werte sind alle nicht-positiv, da q zu jedem Knoten eine Kante der Länge null besitzt und der kürzeste Pfad nicht länger als diese Kante sein kann. Rechts ist der neu gewichtete Graph dargestellt, der entsteht, indem jedes Kantengewicht durch w(u,v) + h(u) − h(v) ersetzt${\displaystyle w(u,v)}$ wird . In diesem neu gewichteten Graphen sind alle Kantengewichte nicht - negativ , und der kürzeste Pfad zwischen zwei beliebigen Knoten verwendet dieselbe Kantenfolge wie der kürzeste Pfad zwischen denselben zwei Knoten im ursprünglichen Graphen. Der Algorithmus schließt mit der Anwendung des Dijkstra-Algorithmus auf jeden der vier Startknoten im neu gewichteten Graphen.

Im neu gewichteten Graphen wird allen Pfaden zwischen zwei Knoten s und t der gleiche Wert h ( s ) − h ( t ) hinzugefügt. Die obige Aussage lässt sich wie folgt beweisen: Sei p ein Pfad .${\displaystyle s-t}$ Sein Gewicht W im neu gewichteten Graphen ist durch folgenden Ausdruck gegeben:

$${\displaystyle \left(w(s,p_{1})+h(s)-h(p_{1})\right)+\left(w(p_{1},p_{2})+h(p_{1})-h(p_{2})\right)+...+\left(w(p_{n},t)+h(p_{n})-h(t)\right).}$$

Jedes wird im vorherigen Ausdruck in Klammern durch aufgehoben; daher bleibt uns folgender Ausdruck für W übrig : ${\displaystyle +h(p_{i})}$${\displaystyle -h(p_{i})}$

$${\displaystyle \left(w(s,p_{1})+w(p_{1},p_{2})+\cdots +w(p_{n},t)\right)+h(s)-h(t)}$$

Der Ausdruck in Klammern ist das Gewicht von p in der ursprünglichen Gewichtung.

Da die Neugewichtung das Gewicht jedes Pfades um denselben Betrag erhöht ,${\displaystyle s-t}$ ist ein Pfad in der ursprünglichen Gewichtung genau dann ein kürzester Pfad, wenn er auch nach der Neugewichtung ein kürzester Pfad ist. Die Gewichte der Kanten, die zu einem kürzesten Pfad von Knoten q zu einem beliebigen Knoten gehören, sind null . Daher sind die Längen der kürzesten Pfade von Knoten q zu jedem Knoten im neugewichteten Graphen null; sie bleiben jedoch kürzeste Pfade. Folglich kann es keine negativen Kanten geben: Hätte die Kante uv nach der Neugewichtung ein negatives Gewicht, würde der Pfad von q nach u mit der Länge null zusammen mit dieser Kante einen Pfad von q nach v mit negativer Länge bilden , was der Tatsache widerspricht, dass alle Knoten den Abstand null zu q haben . Das Nichtvorhandensein negativer Kanten gewährleistet die Optimalität der vom Dijkstra-Algorithmus gefundenen Pfade. Die Distanzen im ursprünglichen Graphen können aus den vom Dijkstra-Algorithmus im neugewichteten Graphen berechneten Distanzen durch Umkehrung der Neugewichtungstransformation ermittelt werden. ^{[ 1 ]}

Die Zeitkomplexität dieses Algorithmus, der Fibonacci-Heaps in der Implementierung des Dijkstra-Algorithmus verwendet, beträgt : Der Algorithmus benötigt Zeit für die Bellman-Ford-Phase und für jede Instanziierung des Dijkstra-Algorithmus. Wenn der Graph dünn besetzt ist , kann die Gesamtzeit daher kürzer sein als die des Floyd-Warshall-Algorithmus , der dasselbe Problem in Zeit löst . ^{[ 1 ]}${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$${\displaystyle O(|V||E|)}$${\displaystyle O(|V|\log |V|+|E|)}$${\displaystyle |V|}$${\displaystyle O(|V|^{3})}$

• Boost: Kürzeste Wege für alle Paare