Frage zu Dijkstras Algorithmus

[algernong]

Hi,
gleicher Beitrag wie im Chit-Chat:

Dijkstra kommt nicht mit negativen Kantengewichten zurecht. Ein Beispiel, an dem Dijkstra fehlschlagen soll, ist zum Beispiel folgender Graph (V, E) mit Kostenfunktion c und Startknoten 1:

V = (1, 2, 3)
E = ((1, 2), (1, 3), (3, 2)), 
c(1, 2) = 1, c(1, 3) = 2, c(3, 2) = -2

Der kuerzeste Weg von 1 zu 2 ist also der Pfad ((1, 3), (3, 2)) mit Gewicht 0.

Mit einer Prioritaetsliste Q und Startknoten s habe ich folgende Referenz-Implementierung von Dijkstra fuer einen Graphen G = (V, E):

Function Dijkstra(s: NodeId)
    d = <infty, ..., infty>
    parent = <null, ..., null>
    d[s] := 0
    parent[s] := s
    Q.insert(s)

    while Q != empty do
        u := Q.deleteMin
        foreach e = (u, v) in E do
            if d[u] + c(e) < d[v] then 
                d[v] := d[u] + c(e)
                parent[v] := u
                if v in Q then Q.decreaseKey(v)
                else Q.insert(v)
    
    return (d, parent)

Inwiefern schlaegt der Algorithmus fuer das Beispiel fehl? Ich sehe das so:
Knoten s = 1 wird in Q eingefuegt. Ausgehende Kanten sind (1, 2) und (1, 3), beide werden in der foreach Schleife entdeckt und relaxiert. Dabei werden die Knoten 2 und 3 in Q eingefuegt, ausserdem wird d[2] = 1 und d[3] = -2 gesetzt. Da c(1, 2) < c(1, 3) wird im naechsten Durchlauf der while Schleife also Knoten 2 untersucht; es gibt keine ausgehende Kanten, und damit wird die foreach Schleife ueberhaupt nicht ausgefuehrt. Also wird Knoten 3 zuletzt betrachtet. Jetzt entdeckt die foreach Schleife aber die Kante (3, 2) und relaxiert, da d[3] + c(3, 2) = 2 - 2 = 0 < 1 = d[2] wird d[2] = 0 gesetzt und Knoten 2 wird erneut in Q eingefuehrt (es passiert aber dann nichts mehr). Also liefert der Algorithmus zuletzt das Ergebnis

d[1] = 0, d[2] = 0, d[3] = 2,

und das ist korrekt.

Die Implementierung stammt aus einem Buch ueber Algorithmen, das Beispiel (oder ein aehnliches) gibt es auf zahlreichen Internetseiten. Lese ich den Algorithmus irgendwo falsch? Findet jemand ein Beispiel mit negativen Kanten (aber ohne negativen Zyklen), bei dem der Algorithmus versagt?

[Shadow992]

Dein Beispiel ist wenig sinnvoll.
Wenn es nur einen Weg zu einem Knoten gibt, dann kann auch nur dieser eine Weg der einzig Richtige bzw. Kürzeste sein.
Macht also wenig Sinn zyklenfreie Graphen anzusehen.
Wobei man jetzt noch definieren sollte, ob es allgemein um ungerichtete Graphen (davon gehe ich aus) oder um gerichtete Graphen geht.
Bei gerichteten Graphen kann es sehr wohl zyklenfreie Graphen geben bei denen Dijkstra nicht funktioniert.

"Nicht funktioniert" darfst du dir jetzt aber nicht so vorstellen, dass Dijkstra nie terminiert (das sollte er bei richtiger Implementierung sehr wohl), sondern dass die Eigenschaft, die den eigentlich Greedy-Algorithmus Dijkstra so besonders macht, verletzt wird. Nämlich, dass garantiert immer der kürzeste Weg von Punkt A nach Punkt B gefunden wird.

Das kannst du nicht mehr garantieren, stell dir dabei einfach einen derartigen Graphen vor(S=Start, E=Ende=Ziel):


Wenn du darauf Dijkstra anwendest wirst du sehr schnell sehen, dass er das Ergebnis "10" ausspruckt obwohl der andere Weg die Kosten 7 hätte.

Das heißt Dijkstra ist hier jetzt kaputt gegangen.
Dasselbe passiert bei ungerichteten Graphen mit Zyklen (wobei du das ja eigentlich nicht wolltest).

Also zusammengefasst:
Die Definition von Dijkstra sagt, dass immer garantiert der kürzeste Weg in endlicher Zeit gefunden wird, solange alle Kantengewichte positiv sind.

Das heißt wenn man die Definition erweitern auf negative Zahlen will, dann muss man sie so erweitern:
Die Definition von Dijkstra sagt, dass immer garantiert der kürzeste Weg in endlicher Zeit gefunden wird.

Und wenn man jetzt auch nur einen einzigen Fall findet (egal ob zyklisch/nicht zyklisch) wo Knoten A und B verbunden sind, aber der gefundene Weg nicht der Kürzeste ist, dann sagt man "Dijkstra funktioniert nicht". Es kann sehr wohl Sonderfälle geben, wo Dijkstra trotzdem funktioniert, aber die Definition heißt nicht "Es kann der beste Weg gefunden werden" sondern sie ist "Es wird der beste Weg gefunden".

Edit:
Was meinst du eigentlich mit "relaxieren"?
Du benutzt es 2x für unterschiedliche "Aktionen" und der Duden kennt das Wort auch nicht.
Die Seite "fremdworterbuchbung.deacademic.com" schlägt mir für "relaxieren" sogar als Synonyme "erschlaffen, entspannen" vor? xD
Also irgendetwas musst du da fachlich verwechselt haben, weil ich selbst das Wort (wie du es benutzt) auch noch nie in der Mathematik/Informatik gehört/gesehen habe.

[algernong]

Hi,

sorry, das war ohne Skizze doof. Ich wollte folgenden Graphen als Beispiel:

Der kuerzeste Pfad von 1 zu 2 ist also (1, 3, 2) mit Gewicht 0, Dijkstra soll aber als kuerzesten Pfad (1, 2) mit Gewicht 1 erkennen. So, wie ich aber die Implementierung verstehe, funktioniert der Algorithmus aber durchaus mit diesem Beispiel (erkennt also (1, 3, 2) als kuerzesten Pfad). Ebenso finde ich aber auch kein anderes Beispiel (fuer einen gerichteten Graphen), in dem der Algorithmus in der Form von meinem Beitrag nicht funktioniert, solange ich auf negative Zyklen verzichte. Laut Buch muss es das aber geben.

Bei deinem Beispiel sollte aber doch auch das korrekte Ergebnis herauskommen, oder? Ich nummeriere die unbeschrifteten Knoten mit 1, 2, 3, 4 von links nach rechts durch und spiele den Algorithmus einmal mit Startknoten S durch:

Vor der ersten Iteration: d[S] = 0, parent[S] = S, Q = <S>
In der ersten Iteration (u = S): S fliegt aus Q, Kanten zu Knoten E und 1 werden entdeckt und in Q eingefuegt.
Vor der zweiten Iteration: d[E] = 10, d[1] = 111, parent[E] = S, parent[1] = S, Q = <E, 1> (Minimum E)
In der zweiten Iteration (u = E): Nichts passiert, E hat keine ausgehende Kanten, also macht das foreach nichts.
Vor der dritten Iteration: d, parent wie gehabt, Q = <1>
... jetzt laeuft der Algorithmus also die Knoten 1, 2, 3 ab. Irgendwann kommt die Iteration in der Knoten 4 angesehen wird, also u = 4. In der foreach Schleife wird die Kante (4, E) (also von 4 zu E) erkannt, und da d[E] = 10 < d[4] + c(4, E), wird die Distanz auf das richtige Ergebnis verringert.
Also stimmt das Ergebnis?

Mit relaxieren habe ich den Code in der foreach-Schleife gemeint, also

            if d[u] + c(e) < d[v] then 
                d[v] := d[u] + c(e)
                parent[v] := u

So wird das auch auf Wikipedia genannt: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus (Informelle Darstellung > Algorithmus > 2. > 3.)

Ist dieser Wert für einen Knoten kleiner als die dort gespeicherte Distanz, aktualisiere sie und setze den aktuellen Knoten als Vorgänger.
Dieser Schritt wird auch als Update oder Relaxieren bezeichnet.

Edit: Wenn ich den Pseudocode auf Wikipedia betrachte, kommt dort wirklich das falsche Ergebnis raus, denn Kanten zu schon abgearbeiteten Knoten werden dort nicht mehr betrachtet. Bei dem Code aus dem Buch werden aber immer alle ausgehenden Kanten betrachtet, und schon abgearbeiteten Knoten koennen problemlos ein zweites mal in Q eingefuegt werden.

[Shadow992]

Ich bin mal ehrlich und habe deinen Beitrag nicht groß durchgelesen, bevor ich hier aber versuche Erklärungen zu geben und dein Problem genau zu betrachten, zitiere ich einfach aus meinem E-Book, weil ich es recht viel anderes als es dadrin steht sowieso nicht erklären würde.
Ein paar Sätze können unwichtig wirken, weil dir der Kontext fehlt, ich versuche aber das unwichtige Zeugs rauszukürzen:

Mit diesem Kapitel kommen wir dem eigentlichen Thema dieses Buches schon ein großes
Stück näher. Diesmal eröffnen wir das Kapitel mit einer Definition der Greedy Algorithmen:
Ein Greedy Algorithmus, auch gieriger Algorithmus genannt, ist ein Algorithmus, der versucht ein Problem zu lösen, indem der Folgezustand ausgewählt wird, der im aktuellen Zustand am vielversprechendsten aussieht. Um die Definition besser zu verstehen nehmen wir die Aufgabenstellung: ”Finde den kürzesten Weg von Knoten A nach Knoten B” und suchen einen Greedy Algorithmus, der dieses Problem löst. Wir werden uns in diesem Buch auf den Dijkstra Algorithmus beschränken, da er sehr effizient ist, gleichzeitig einfach zu verstehen und ebenso einfach
zu implementieren.

[...]

Zuerst einmal müssen wir die Idee hinter Dijkstra verstanden haben, bevor wir ihn programmieren können. Dijkstra basiert auf einer sehr einfachen Idee: Wir verfolgen nicht jeden möglichen Pfad bis zum Ende, sondern wir verfolgen nur die Pfade bis zum Ende, die momentan kleiner als unser kürzester Pfad zum Zielknoten sind.
Wir suchen uns also ganz am Anfang den kürzesten Pfad, der entsteht wenn wir von unserem Startknoten aus weitergehen. Also nehmen wir am Anfang den Knoten mit der kürzesten Distanz. Dieser Knoten wird unser nächster aktueller Knoten. Jetzt schauen wir alle Knoten des aktuellen Knotens an und fügen jeden Pfad, den wir gehen können in unsere Liste hinzu. Anschließend betrachten wir alle Pfade (sowohl die Aktuellen als
auch die Neuen), die wir hätten gehen können, suchen uns den Pfad mit der geringsten Distanz aus und setzen diesen Pfad zu unserem aktuellen Pfad, der letzte Knoten von diesem Pfad ist anschließend unser aktueller Knoten.
Am einfachsten kann man sich das so vorstellen: Wir speichern alle Pfade, die wir bisher hätten gehen können mit ihren Distanzen (=Kosten) und machen immer beim kürzesten Pfad weiter. Sobald der kürzeste Pfad den Zielknoten erreicht hat, können die anderen Pfade nie mehr kürzer werden als der Kürzeste und damit können wir unseren Algorithmus abbrechen und den kürzesten Pfad zurückgeben. Mit diesem Algorithmus spart man im schlechtesten Falle (= Worst-Case) natürlich gar nichts, weil der Algorithmus dann trotzdem alle Pfade aufstellt und durchläuft. Im Durchschnittsfall jedoch, sparen wir uns jede Menge Pfade, die wir andernfalls berechnen müssten. Das mag auf
den ersten Blick nur schwer ersichtlich sein, hat man einen recht großen Graphen und liegt der Startknoten sehr nahe am Zielknoten, kann man den Effekt sehr gut sehen, wer will kann das ja auch einmal mit Hand und Papier durchgehen.

[...]

Dijkstra hat als großen Vorteil, dass wenn einmal ein extrem kurzer Pfad gefunden
wurde vom Start zum Zielknoten, meistens sehr schnell alle anderen Pfade verworfen
werden können, da sie schon eine größere Distanz aufweisen als der Pfad, den man bereits
gefunden hat. Der Dijkstra Algorithmus ist zwar nicht großartig ”intelligent” und doch
effizienter als Tiefen-/Breitensuche. Will man den kürzesten Pfad ohne Dijkstra finden
und nur auf Tiefen-/Breitensuche setzen, muss man erst einmal jeden möglichen Pfad von
dem Anfangsknoten zum Zielknoten bestimmen, anschließend alle Distanzen der Pfade
mit einander vergleichen und den Pfad mit der kleinsten Distanz heraussuchen.

Quelle:
"Einführung in die Programmierung von Künstlicher Intelligenz", Kapitel 4.2

Falls die Erklärung etwas zu sehr aus dem Kontext gerissen ist (ich denke die Abbildung dazu fehlt doch schon irgendwie) kannst du dir das Ganze auch im kostenlosen E-Book anschauen, da habe ich es auch an einem Beispiel durchexerziert.

Edit:
Noch als kleine Amerkung auf dein Problem bezogen:
Die Idee von Dijkstra ist es Wege, die niemals kürzer als der aktuelle kürzeste Pfad zum Endknoten werden können direkt rauszuschmeißen.

Daher wird Dijkstra für mein Beispiel ganz grob so ablaufen:
2 Pfade werden gefunden:
- Von S nach E in 10
- Von S nach 1 in 111

Jetzt sagt Dijkstra aber: "Ich bin ja nicht blöd, wenn ich nur positive Kantengewichte habe, dann kann der Weg S -> 1 niemals kleiner als 111 werden und damit ist S -> E definitiv der kürzeste Weg, weil es keine anderen Knoten mehr gibt, der von S aus erreichbar ist und 10 definitiv kürzer ist als 111, selbst wenn die restlichen Kantengewichte 0 sind."

Das heißt der ganze Algorithmus steht und fällt mir der Bedingung "nur positive Kantengewichte".

[algernong]

Hi,

danke fuer deine Antwort. Mir geht es sehr um die Implementierung, die ich in meinem ersten Beitrag geschrieben habe. Dort sehe ich naemlich das

Jetzt sagt Dijkstra aber: "Ich bin ja nicht blöd, wenn ich nur positive Kantengewichte habe, dann kann der Weg S -> 1 niemals kleiner als 111 werden und damit ist S -> E definitiv der kürzeste Weg, ..."

nicht. Die Laufzeit ist aber |V|log|V| + |E| (mit Q als Fibonacci Heap), und damit nicht langsamer als der ganz normale Dijkstra Algorithmus. Demnach wuerde ich eigentlich annehmen, dass auch genau diese Implementierung irgendwo mit negativen Kanten (aber ohne negativen Zyklen) fehlschaegt - ich finde aber kein solches Beispiel. (Und die bisherigen Beispiele funktionieren wenn ich sie am Code durchspiele)

[Shadow992]

Originally Posted by algernong

Hi,

danke fuer deine Antwort. Mir geht es sehr um die Implementierung, die ich in meinem ersten Beitrag geschrieben habe. Dort sehe ich naemlich das

nicht. Die Laufzeit ist aber |V|log|V| + |E| (mit Q als Fibonacci Heap), und damit nicht langsamer als der ganz normale Dijkstra Algorithmus. Demnach wuerde ich eigentlich annehmen, dass auch genau diese Implementierung irgendwo mit negativen Kanten (aber ohne negativen Zyklen) fehlschaegt - ich finde aber kein solches Beispiel. (Und die bisherigen Beispiele funktionieren wenn ich sie am Code durchspiele)

Ich tu mich zwar sehr schwer deinen Code zu lesen/zu verstehen (Ich hasse diese Syntax wirklich Abgrundtief). Aber wenn ich das richtig verstanden habe, zeigt dir der Code nicht den kürzesten Weg von X -> Y, was man normalerweise bei Dijkstra will (zumindest in 95% der Fälle).
Sondern den kürzesten Weg von Knoten X zu jedem anderen Knoten.

Dadurch umgehst du natürlich das Problem gewissermaßen. Vielleicht ist bei dieser Herangehensweise das ganze "positive Gewichte"-Problem auch beseitigt, zumindest weitestgehend.

Dann aber stehst du einem anderen Problem gegenüber. Nämlich dem eigentlichen Vorteil von Dijkstra. Dijkstra wird ja eben dafür benutzt sehr früh möglichst viele Knoten auszuschließen. Damit ich in einem Graphen mit 100.000 Knoten nicht alle 100.000 anschauen muss, sondern vielleicht nur 20 (weil Start und Ziel sehr nahe beieinander liegen).
Was du hier also opferst, dafür dass du auch einige Fälle mit negativen Kantengewichten behandeln kannst, ist jede Menge Geschwindigkeit.

Also kurz um, es kann sein, dass Dijkstra in einigen Fällen nicht kaputt geht, wenn man die kürzesten Pfade zu allen Knoten betrachtet und vielleicht klappt das ohne Zyklen auch gar nicht mehr.
Aber Dijkstra, wie man ihn in der freien Wildbahn trifft mit der Intention den kürzesten Weg zwischen 2 Knoten zu finden, kann auch bei zyklenfreien Graphen kaputt gehen.

Und das unabhängig von der Implementierung.