Frage zu Dijkstras Algorithmus

10/02/2015 02:36 algernong#1

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:

Code:

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):

Code:

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

Code:

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?

10/02/2015 16:39 Shadow992#2

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):
[Only registered and activated users can see links. Click Here To Register...]

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. :D

10/02/2015 18:51 algernong#3

Hi,

sorry, das war ohne Skizze doof. Ich wollte folgenden Graphen als Beispiel:
[Only registered and activated users can see links. Click Here To Register...]
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

Code:

            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.)

Quote:

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.

10/02/2015 19:07 Shadow992#4

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. :D
Ein paar S�tze k�nnen unwichtig wirken, weil dir der Kontext fehlt, ich versuche aber das unwichtige Zeugs rauszuk�rzen:

Quote:

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
[Only registered and activated users can see links. Click Here To Register...]

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".

10/04/2015 17:56 algernong#5

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

Quote:

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)

10/04/2015 20:08 Shadow992#6

Quote:

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.