Dijkstra-Algorithmus
Der Dijkstra-Algorithmus findet in einem Graphen den kürzesten Weg von einem Knoten zu einem anderen. Zu diesem Algorithums gibt es eine wunderschöne Geschichte:
Es war einmal ein chinesischer Kaiser, der hiess Priori-Tii Kiu. Er wollte wissen, wie er zu jeder grossen Stadt seines Reiches auf dem schnellsten Wege gelangen könne, denn er war ein guter Kaiser; hätte es irgendwo in seinem Land gebrannt, wäre er auf dem schnellsten Wege dort und könnte den Leuten Trost spenden. Doch wie konnte er nur herausfinden, welches die schnellsten Wege in seinem Land waren?
Ihm kam einst die Idee, dass er eine Person losschicken könnte, die jeden Weg aus einer Stadt heraus einmal abschreiten solle, um die Zeit zu messen, und dies bei jeder Stadt im ganzen Land. Doch als die Person nach einem Jahr völlig erschöpft zum Kaiser kam und ihm berichtete, dass sie erst 10 der 10000 Städte besucht habe und völlig erschöpft sei, beauftragte er seine Gelehrten mit diesem Problem, und die überlegten lange, wie sie eine schnellere Lösung finden wollten.
Als den Gelehrten schliesslich die Köpfe rauchten, brauchten sie eine Zigarettenpause. Zur Erfrischung tischte ihnen die schöne Kaiserstochter Dijkstra Lotusbier auf. Es waren aber sehr viele Gelehrte, weshalb sie, um alle zu bedienen, viel zu lange gebraucht hätte. Die schlaue Tochter jedoch fragte jeden Gelehrten, den sie schon bedient hatte, ob er nicht ebenso einige Gelehrte bedienen könnte. So konnten alle Gelehrte innerst kürzester Zeit bedient werden.
Der junge Gelehrte Schor-Test Paf, der schon lange mit der schönen Tochter liebäugelte, beobachtete sie interessiert, wie sie so schnell alle Gelehrten bedienen konnte. Und da fiel bei ihm der Groschen und er rief sofort alle Gelehrten in den Hörsal zurück, um weiterzubesprechen. Dijkstra war über diese Undankbarkeit so beleidigt, dass sie weinend auf ihr Zimmer floh (nachdem sie sich noch einige Lotus-Biere gönnte). Schor-Test Paf jedoch erzählte den anderen von seiner Entdeckung. Nur wenige Stunden später konnten die Gelehrten ihrem Kaiser eine Befehlsrolle übergeben, mit der er innert kürzester Zeit alle Wege des Landes kennen würde. Die Befehle waren die folgenden:
- Es sollen sich in der Stadt, in der der Kaiser wohnt, soviele Leute, wie es Wege aus der Stadt raus gibt, freiwillig melden, die sich guter Gesundheit erfreuen und einen Zeitmesser besitzen. Allen Teilnehmern wird ein Blatt Papier verteilt, auf dem als einzige Zeile der Name der Hauptstadt zu lesen war.
- Diese Leute sollen sich alle zur gleichen Zeit vom Mittelpunkt der Stadt aus auf den Weg machen, jeder in eine andere Richtung, hinaus aus der Stadt.
- Wenn einer dieser Leute in der nächsten Stadt ankommt, so solle er sich die Zeit merken, die er für den ganzen Weg brauchte. Daraufhin meldet er sich beim Stadtverwalter.
- Wenn der Ankommende der erste war, der mit diesem Auftrag vom Kaiser kam, so bittet er den Stadtverwalter, so schnell wie möglich wiederum so viele Leute aufzutreiben, wie es Wege aus der Stadt gibt. Sodann sollen diese Leute das gleiche machen, wie ab Punkt 2, wobei jeder von ihnen eine Kopie der Liste bekommt, die der Ankommende mitgebracht hat, und bei dem zuunterst der Name der Stadt hinzugefügt wurde. Der Ankommende selbst solle sich zwei Lotusbier gönnen und sich auf den Weg in die Hauptstadt machen, um dem Kaiser von seiner Reisezeit und dem Weg, den die Liste beschreibt zu berichten.
- Wenn der Stadtverwalter dem Ankommenden berichten kann, dass vor ihm bereits jemand mit dem gleichen Auftrag da war, so soll er sich ein Lotusbier gönnen und sich nach Hause begeben, sein Auftrag ist hiermit erledigt.
Als der Kaiser dies las, schmunzelte er und dachte, dass seine Gelehrten verrückt waren, denn selbst das Import-Gesetz für die Einführung von Karamel-Bonbons beinhaltete mehr Anweisungen. Er fragte sie deshalb, wer diesen Einfall hatte, und Schor-Test Paf meldete, dass dies einzig und allein der Verdienst seiner bildhübschen Tochter Djikstra sei; er habe erst durch ihre Klugheit diesen grandiosen Einfall gehabt. Diese Worte gaben dem Kaiser zu denken und er las die Befehle nochmals durch, er konnte jedoch keinen Sinn in den Befehlen entdecken. Sodann sprach er, dass man diese Befehle ausführen solle. Gleichzeitig aber soll jemand den alten Auftrag zu Ende führen. Derjenige Auftrag, der zuerst fertig ist, wird sich als der Schnellste erweisen.
Darauf bereiteten die Gelehrten alles vor, und sie konnten die ersten Personen bereits drei Tage später loslaufen lassen. Und schon bald musste der Kaiser einsehen, dass diese Befehle gar nicht dumm waren, denn er bekam innerst kürzester Zeit Wegbeschreibungen von Städten, in denen der andere Läufer noch nicht einmal die angrenzenden Hügel sehen konnte. So kam es, dass bereits nach einem Jahr alle Städte ausgezählt waren und der Kaiser rief zufrieden seine Gelehrten zu sich. Er sprach: "Diese Befehle waren wohl die schnellsten Befehle, die ich je erlebt habe. Sie sollen deshalb den ehrenvollen Namen Dijkstra-Befehle tragen." Dijkstra, die neben ihrem Vater sass, horchte auf und bat den Vater, den Mann aufzudecken, der ihr diese Ehre erwies. Der Kaiser verstand nicht ganz, wieso sie dies wissen wollte, worauf sie sagte, dass derjenige, der ihren Schaftsinn und ihre Intelligenz zu sehen vermag, auch ihr Ehemann sein möge. Daraufhin zeigte der Kaiser auf Schor-Test Paf und sie war überglücklich, einen so schönen Mann kennenzulernen. Der Kaiser liess die beiden noch in der selben Woche heiraten, und sie lebten glücklich und zufrieden, ganze n^2 Jahre lang.
In einem Computersystem muss die ganze Sache etwas trockener angegangen werden. Hier ist der ganze Graph mit allen Verbindungen und den Kosten einer Verbindung bekannt. Ebenfalls ist bekannt, welche Verbindungen von welchem Knoten ausgehen, und zu welchem Knoten sie führen. Sodann wird folgendermassen verfahren:
- Man starte beim Anfangspunkt.
- In eine Ereignisliste werden alle Knoten mit der jeweiligen Ankunftszeit eingetragen, die von diesem Knoten aus besucht werden können. Die Ankunftszeit ist jeweils die Zeit, die insgesamt seit dem Start des Algorithmus vergangen ist, addiert mit den Verbindungskosten der jeweiligen Verbindung. Ist einer dieser neuen Knoten bereits in der Ereignisliste vertreten, so wird nur derjenige genommen, der die kleinere Ankunftszeit hat.
- Nun wird das unmittelbar nächste Ereignis in der Ereignisliste angeschaut.
- Wenn dieses Ereignis einen noch nicht besuchten Knoten beschreibt, so wird die Ankunftszeit und der gesamte Weg, der gegangen wurde in die endgültige Shortest-Path-Tabelle eingetragen. Darauf wird bei Punkt 2 weitergefahren.
- Wenn dieses Ereignis einen bereits besuchten Knoten beschreibt, so passiert nichts.
Diese Ereignisliste nennt man auch die Priority-Queue, was nichts anderes bedeutet, als dass in dieser Warteschlange (die Ereignisse warten auf ihre Abfertigung) nur die Knoten stehen, die überhaupt momentan erreicht werden können. Die Ereignisliste kann beispielsweise mittels eines Heaps erreicht werden, sodann braucht der gesamte Algorithmus nur O(n log n).
Hier noch ein Beispiel mit den 6 Knoten A bis F:
+------5------+
| |
| /-2--B--3--C--5-\
| / | /| \
+-A 2 /3/ 1 F
\ |/ | /
\-1--D--1--E--2-/
Um eine kleine Verwirrung zu vermeiden: Der Pfad von A nach C mit Grad 5 ist nicht die Zusammenfassung der beiden Pfade A-B und B-C, sondern ein eigenständiger Pfad. Ausserdem sei hier festgelegt, dass die Ereignisliste stets nach den Kosten sortiert ist, dass also das linkeste Ereignis stets das nächste abzuarbeitende ist (anderer Fall: siehe weiter unten).
Dadurch erhält man folgende Liste (Die Zahlen in Klammern geben an, welches die kürzeste Distanz zu diesen Knoten ist). In der Spalte "bereits besucht" sind diejenigen Knoten fettgedruckt, die gerade bearbeitet werden (welche Knoten kann ich von diesem aus erreichen)
| Schritt | bereits besucht | Ereignisliste |
|---|---|---|
| 0 | A | D(1), B(2), C(5) |
| 1 | A,D | B(2), E(2), C(4) |
| 2 | A,D,B | E(2), C(4) |
| 3 | A,D,B,E | C(3), F(4) |
| 4 | A,D,B,E,C | F(4) |
| 5 | A,D,B,E,C,F |
Dadurch erhält man die Shortest-Path-Liste A(0), B(2), C(3), D(1), E(2) und F(4)
Um zusätzlich noch anzugeben, welchen Weg man vom Startknoten (A) zu einem Zielknoten nehmen muss, müsste zu jedem Knoten noch gespeichert werden, von wo man ihn mittels des kürzesten Pfades erreichte. Das bedeutet, dass jedesmal, wenn ein Knoten durch niedrigere Kosten erreicht werden kann, diesem den neuen Herkunftsort eintragen muss. In der folgenden zusätzlichen Tabelle sind die Herkunftsknoten in den eckigen Klammern angegeben:
| Schritt | bereits besucht | Ereignisliste |
|---|---|---|
| 0 | A[.] | D(1)[A], B(2)[A], C(5)[A] |
| 1 | A[.],D[A] | B(2)[A], E(2)[D], C(4)[D] |
| 2 | A[.],D[A],B[A] | E(2)[D], C(4)[D] |
| 3 | A[.],D[A],B[A],E[D] | C(3)[E], F(4)[E] |
| 4 | A[.],D[A],B[A],E[D],C[E] | F(4)[E] |
| 5 | A[.],D[A],B[A],E[D],C[E],F[E] |
Folgendes sind also die kürzesten Pfade: A:A, B:A-B, C:A-D-E-C, D:A-D, E:A-D-E, F:A-D-E-F
Dieses Resultat erhält man am Beispiel des Knotens F: F wird erreicht durch den Knoten E, welcher wiederum erreicht wird vom Knoten D und dieser wiederum kann von A aus erreicht werden. Dadurch entsteht der folgende minimale Spannbaum:
/-2--B C
/ |
A 1 F
\ | /
\-1--D--1--E--2-/
Der Algorithmus funktioniert auch, wenn nicht überprüft wird, ob ein Knoten bereits in der Ereignisliste enthalten ist. Die Liste sieht dann folgendermassen aus:
| Schritt | bereits besucht | Ereignisliste |
|---|---|---|
| 0 | A | D(1), B(2), C(5) |
| 1 | A,D | B(2), E(2), B(3), C(4), C(5) |
| 2 | A,D,B | E(2), B(3), C(4), C(5), C(5) |
| 3 | A,D,B,E | B(3), C(3), C(4), F(4), C(5), C(5) |
| 4 | A,D,B,E | C(3), C(4), F(4), C(5), C(5) |
| 5 | A,D,B,E,C | C(4), F(4), C(5), C(5), F(8) |
| 6 | A,D,B,E,C | F(4), C(5), C(5), F(8) |
| 7 | A,D,B,E,C,F | C(5), C(5), F(8) |
| 8 | A,D,B,E,C,F | C(5), F(8) |
| 9 | A,D,B,E,C,F | F(8) |
| 10 | A,D,B,E,C,F |
Dadurch erhält man ebenfalls die genau gleiche Shortest-Path-Liste A(0), B(2), C(3), D(1), E(2) und F(4). Wie man sieht, ist jedoch der Aufwand grösser. Es lohnt sich also, die Ereignisliste durchzuprüfen.
Wenn nun beim Einsetzen in die Liste auch noch die Überprüfung wegfallen würde, ob ein Knoten nicht schon besucht wurde, so ergäbe sich folgende Liste:
| Schritt | bereits besucht | Ereignisliste |
|---|---|---|
| 0 | A | D(1), B(2), C(5) |
| 1 | A,D | A(2), B(2), E(2), B(3), C(4), C(5) |
| 2 | A,D | B(2), E(2), B(3), C(4), C(5) |
| 3 | A,D,B | E(2), B(3), A(4), C(4), D(4), C(5), C(5) |
| 4 | A,D,B,E | B(3), C(3), D(3), A(4), C(4), D(4), F(4), C(5), C(5) |
| 5 | A,D,B,E | C(3), D(3), A(4), C(4), D(4), F(4), C(5), C(5) |
| 6 | A,D,B,E,C | D(3), A(4), C(4), D(4), E(4), F(4), C(5), C(5), B(6), D(6), A(8), F(8) |
| 7 | A,D,B,E,C | A(4), C(4), D(4), E(4), F(4), C(5), C(5), B(6), D(6), A(8), F(8) |
| 8 | A,D,B,E,C | C(4), D(4), E(4), F(4), C(5), C(5), B(6), D(6), A(8), F(8) |
| 9 | A,D,B,E,C | D(4), E(4), F(4), C(5), C(5), B(6), D(6), A(8), F(8) |
| 10 | A,D,B,E,C | E(4), F(4), C(5), C(5), B(6), D(6), A(8), F(8) |
| 11 | A,D,B,E,C | F(4), C(5), C(5), B(6), D(6), A(8), F(8) |
| 12 | A,D,B,E,C,F | C(5), C(5), B(6), D(6), E(6), A(8), F(8), C(9) |
| 13 | A,D,B,E,C,F | C(5), B(6), D(6), E(6), A(8), F(8), C(9) |
| 14 | A,D,B,E,C,F | B(6), D(6), E(6), A(8), F(8), C(9) |
| 15 | A,D,B,E,C,F | D(6), E(6), A(8), F(8), C(9) |
| 16 | A,D,B,E,C,F | E(6), A(8), F(8), C(9) |
| 17 | A,D,B,E,C,F | A(8), F(8), C(9) |
| 18 | A,D,B,E,C,F | F(8), C(9) |
| 19 | A,D,B,E,C,F | C(9) |
| 20 | A,D,B,E,C,F |
Und wiederum erhält man die Shortest-Path-Liste A(0), B(2), C(3), D(1), E(2) und F(4). Aber wie man sieht, ist der Aufwand jetzt erheblich grösser. Es lohnt sich also sicher, die Besucht-Liste durchzuprüfen
Als letzten Punkt und als Überleitung zum Dijkstra mit negativen Kosten sei hier noch aufgeführt, was passiert, wenn die Ereignisliste nicht nach den Kosten sortiert wird. In den oberen Beispielen wurde der Einfachheit halber immer angenommen, es sei bekannt, welches das nächste Ereignis (das mit den niedrigsten Kosten) ist. Was ohne diese Sortierung zusätzlich dazukommen muss, ist, dass für jeden Knoten bekannt sein muss, welches die bisherige Bestzeit war, mit welchem der Knoten erreicht werden kann. Programmiertechnisch kann man dies am besten lösen, indem man für jeden Knoten von Anfang an einen möglichst hohen Anfangswert speichert (hier 99), der mit Sicherheit nicht überschritten werden wird.
Und folgendes ist die Anweisung, welches der Computer bei jedem Schritt auszuführen hat: Nehme das erstbeste Ereignis und überprüfe, ob der Knoten dadurch schneller erreicht werden kann. Wenn ja, so füge sämtliche Knoten, die von diesem aus erreicht werden können, als neues Ereignis ein. Wenn nein, so tue nichts. Dass sämtliche Knoten nochmals eingetragen werden müssen hat einen Grund: Es könnte ja sein, dass ohne eine Sortierung ein Knoten erreicht wird, der bereits früher mal besucht wurde, jetzt jedoch durch den neuen Pfad viel schneller erreicht wird. So könnte es doch sein, dass andere Knoten, die von diesem aus angesprochen werden, ebenfalls bereits früher abgearbeitet worden sind und nun jedoch durch den neuen Pfad ebenfalls viel schneller erreicht werden können. Fortsetzung, siehe Dijkstra mit negativen Kosten.
| Schritt | bereits besucht | Ereignisliste |
|---|---|---|
| 0 | A(0),B(99),C(99),D(99),E(99),F(99) | B(2), C(5), D(1) |
| 1 | A(0),B(2),C(99),D(99),E(99),F(99) | C(5), D(1), A(4), C(5), D(4) |
| 2 | A(0),B(2),C(5),D(99),E(99),F(99) | D(1), A(4), C(5), D(4), A(10), B(8), D(8), E(6), F(10) |
| 3 | A(0),B(2),C(5),D(1),E(99),F(99) | A(4), C(5), D(4), A(10), B(8), D(8), E(6), F(10), A(2), B(3), C(4), E(2) |
| 4 | A(0),B(2),C(5),D(1),E(99),F(99) | C(5), D(4), A(10), B(8), D(8), E(6), F(10), A(2), B(3), C(4), E(2) |
| 5 | A(0),B(2),C(5),D(1),E(99),F(99) | D(4), A(10), B(8), D(8), E(6), F(10), A(2), B(3), C(4), E(2) |
| 6 | A(0),B(2),C(5),D(1),E(99),F(99) | A(10), B(8), D(8), E(6), F(10), A(2), B(3), C(4), E(2) |
| 7 | A(0),B(2),C(5),D(1),E(99),F(99) | B(8), D(8), E(6), F(10), A(2), B(3), C(4), E(2) |
| 8 | A(0),B(2),C(5),D(1),E(99),F(99) | D(8), E(6), F(10), A(2), B(3), C(4), E(2) |
| 9 | A(0),B(2),C(5),D(1),E(99),F(99) | E(6), F(10), A(2), B(3), C(4), E(2) |
| 10 | A(0),B(2),C(5),D(1),E(6),F(99) | F(10), A(2), B(3), C(4), E(2), C(7), D(7), F( 8) |
| 11 | A(0),B(2),C(5),D(1),E(6),F(10) | A(2), B(3), C(4), E(2), C(7), D(7), F(8), C(15), E(12) |
| 12 | A(0),B(2),C(5),D(1),E(6),F(10) | B(3), C(4), E(2), C(7), D(7), F(8), C(15), E(12) |
| 13 | A(0),B(2),C(5),D(1),E(6),F(10) | C(4), E(2), C(7), D(7), F(8), C(15), E(12) |
| 14 | A(0),B(2),C(4),D(1),E(6),F(10) | E(2), C(7), D(7), F(8), C(15), E(12), A(9), B(7), D(7), E(5), F(9) |
| 15 | A(0),B(2),C(4),D(1),E(2),F(10) | C(7), D(7), F(8), C(15), E(12), A(9), B(7), D(7), E(5), F(9), C(3), D(3), F(4) |
| 16 | A(0),B(2),C(4),D(1),E(2),F(10) | D(7), F(8), C(15), E(12), A(9), B(7), D(7), E(5), F(9), C(3), D(3), F(4) |
| 17 | A(0),B(2),C(4),D(1),E(2),F(10) | F(8), C(15), E(12), A(9), B(7), D(7), E(5), F(9), C(3), D(3), F(4) |
| 18 | A(0),B(2),C(4),D(1),E(2),F(8) | C(15), E(12), A(9), B(7), D(7), E(5), F(9), C(3), D(3), F(4), C(13), E(10) |
| 19 | A(0),B(2),C(4),D(1),E(2),F(8) | E(12), A(9), B(7), D(7), E(5), F(9), C(3), D(3), F(4), C(13), E(10) |
| 20 | A(0),B(2),C(4),D(1),E(2),F(8) | A(9), B(7), D(7), E(5), F(9), C(3), D(3), F(4), C(13), E(10) |
| 21 | A(0),B(2),C(4),D(1),E(2),F(8) | B(7), D(7), E(5), F(9), C(3), D(3), F(4), C(13), E(10) |
| 22 | A(0),B(2),C(4),D(1),E(2),F(8) | D(7), E(5), F(9), C(3), D(3), F(4), C(13), E(10) |
| 23 | A(0),B(2),C(4),D(1),E(2),F(8) | E(5), F(9), C(3), D(3), F(4), C(13), E(10) |
| 24 | A(0),B(2),C(4),D(1),E(2),F(8) | F(9), C(3), D(3), F(4), C(13), E(10) |
| 25 | A(0),B(2),C(4),D(1),E(2),F(8) | C(3), D(3), F(4), C(13), E(10) |
| 26 | A(0),B(2),C(3),D(1),E(2),F(8) | D(3), F(4), C(13), E(10), A(8), B(6), D(6), E(4), F(8) |
| 27 | A(0),B(2),C(3),D(1),E(2),F(8) | F(4), C(13), E(10), A(8), B(6), D(6), E(4), F(8) |
| 28 | A(0),B(2),C(3),D(1),E(2),F(4) | C(13), E(10), A(8), B(6), D(6), E(4), F(8), C(9), E(6) |
| 29 | A(0),B(2),C(3),D(1),E(2),F(4) | E(10), A(8), B(6), D(6), E(4), F(8), C(9), E(6) |
| 30 | A(0),B(2),C(3),D(1),E(2),F(4) | A(8), B(6), D(6), E(4), F(8), C(9), E(6) |
| 31 | A(0),B(2),C(3),D(1),E(2),F(4) | B(6), D(6), E(4), F(8), C(9), E(6) |
| 32 | A(0),B(2),C(3),D(1),E(2),F(4) | D(6), E(4), F(8), C(9), E(6) |
| 33 | A(0),B(2),C(3),D(1),E(2),F(4) | E(4), F(8), C(9), E(6) |
| 34 | A(0),B(2),C(3),D(1),E(2),F(4) | F(8), C(9), E(6) |
| 35 | A(0),B(2),C(3),D(1),E(2),F(4) | C(9), E(6) |
| 36 | A(0),B(2),C(3),D(1),E(2),F(4) | E(6) |
| 37 | A(0),B(2),C(3),D(1),E(2),F(4) |
Wie man sieht, ist der Aufwand enorm. Er könnte höchstens etwas abgeschwächt werden, indem man denjenigen Knoten, von dem aus man einen neuen besucht hat, nicht wieder in die Ereignisliste aufnimmt. Dies bringt jedoch formal betrachtet keine wirkliche Besserung. Und das ist ein Problem, denn genau diese Anweisung wird beim folgenden Thema gebraucht:
Dijkstra mit neagtiven Kosten
Gerade das letzte Beispiel führt in das Thema der negativen Kosten ein: Tatsächlich funktioniert der Algorithmus nur mit positiven Zahlen stets fehlerfrei, es gibt jedoch auch viele Beispiele, bei denen es mit negativen Zahlen funktioniert. Der Grund für ein Nicht-Funktionieren liegt in der Priority-Queue: Bei negativen Werten entsteht selbst mit sortierter Ereignisliste das Problem, dass ein Knoten durch einen (mit positiven Werten bestückten) Weg erreicht wird und erst später durch einen anderen (mit einigen negativen Werten bestückten) erreicht wird. Nun kann es wie schon im letzten Beispiel sein, dass die Kosten des 2. Weges insgesamt kleiner sind, als die des ersten Weges.
Durch Weglassen des Anweisungs-Punktes 5 des Algorithmus ("Wenn dieses Ereignis einen bereits besuchten Knoten beschreibt, so passiert nichts") besteht keine Priority-Queue mehr und es entsteht genau die Anweisung zum letzteren Beispiel. Nun besteht jedoch das Problem des Abbruchkriteriums: Unter diesen Umständen ist es wie bereits gesehen notwendig, viele Knoten mehrmals zu besuchen, was dem Algorithmus eine sehr hohe (bis unendliche) Laufzeit einbringt. Zum unendlich: Man stelle sich folgende zwei Knoten vor:
Knoten A hat einen Weg nach B mit Kosten 1
Knoten A hat einen Weg nach B mit Kosten -2
Knoten B hat einen Weg nach A mit Kosten 1
Mit der Priority-Queue würde der Algorithmus nach einem Schritt terminieren mit dem Resultat -2 (er nimmt den 2. Weg von A nach B). Ohne die Priority-Queue würde er nach dem 1. Schritt herausfinden, dass er A mit den Gesamtkosten -1 erreichen kann (Von A nach B mit Kosten -2 und dann von B nach A mit Kosten 1). Sodann findet er den Weg ABAB mit Kosten -2 + 1 + -2, also -3, usw.... Für dieses Netz von Knoten wird der Algorithmus niemals terminieren, weil er stets einen neuen, noch schnelleren Weg findet (genaugenommen terminiert er bei dem kleinsten Wert, der durch ein Integer dargestellt werden kann, denn der gleich darauffolgende Schritt würde zu einem Wrap-Around führen und somit den maximalen Wert eines Integers angeben.