{"id":20028,"date":"2021-03-12T09:00:00","date_gmt":"2021-03-12T08:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=20028"},"modified":"2025-06-12T09:17:39","modified_gmt":"2025-06-12T07:17:39","slug":"bellman-ford-algorithmus-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/bellman-ford-algorithmus-java\/","title":{"rendered":"Bellman-Ford-Algorithmus (mit Java-Beispiel)"},"content":{"rendered":"\n<p>In den ersten zwei Teilen dieser Serie \u00fcber Shortest-Path-Algorithmen hast du den <a href=\"\/de\/algorithmen\/dijkstra-algorithmus-java\/\">Dijkstra-<\/a> und den <a href=\"\/de\/algorithmen\/a-stern-algorithmus-java\/\">A*-Algorithmus<\/a> kennengelernt.<\/p>\n\n\n\n<p>Beide Algorithmen sind nur auf Graphen anwendbar, die <em>keine negativen Kantengewichte<\/em> haben. Was das bedeutet \u2013 und wie der Bellman-Ford-Algorithmus damit umgeht, erf\u00e4hrst du in diesem Artikel.<\/p>\n\n\n\n<p>Folgende Fragen werden gekl\u00e4rt:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Was bedeutet \"negatives Kantengewicht\"?<\/li>\n\n\n\n<li>Wo kommen negative Kantengewichte in der Praxis vor? <\/li>\n\n\n\n<li>Warum sind Dijkstra und A* bei negativen Kantengewichten nicht anwendbar?<\/li>\n\n\n\n<li>Wie funktioniert der Bellman-Ford-Algorithmus (Schritt f\u00fcr Schritt an einem Beispiel erkl\u00e4rt)?<\/li>\n\n\n\n<li>Was ist ein \"negativer Zyklus\", und wie geht man damit um?<\/li>\n\n\n\n<li>Wie implementiert man den Bellman-Ford-Algorithmus in Java?<\/li>\n\n\n\n<li>Wie bestimmt man die Zeitkomplexit\u00e4t des Bellman-Ford-Algorithmus?<\/li>\n<\/ul>\n\n\n\n<p>Den Quellcode der gesamten Artikelserie \u00fcber Pathfinding-Algorithmen findest du <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\" target=\"_blank\" rel=\"noopener\">in diesem GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"was-ist-ein-negatives-kantengewicht\">Was ist ein negatives Kantengewicht?<\/h2>\n\n\n\n<p>In den vorangegangenen Teilen habe ich beispielhaft gezeigt, wie eine Stra\u00dfenkarte auf einen gewichteten Graphen abgebildet wird:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"425\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph.png\" alt=\"Pathfinding: Abbildung einer Stra\u00dfenkarte auf einen kantengewichteten Graphen\" class=\"wp-image-20043\" style=\"width:800px;height:283px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-224x79.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-336x119.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-504x179.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-672x238.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-400x142.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-600x213.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-800x283.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-streetmap-graph-944x334.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Pathfinding: Abbildung einer Stra\u00dfenkarte auf einen kantengewichteten Graphen<\/figcaption><\/figure>\n<\/div>\n\n\n<p>In diesem Graphen geben die Gewichte (die Zahlen an den Kanten) an, wie hoch die Kosten f\u00fcr einen bestimmten Pfad sind. Dies kann beispielsweise die Zeit in Minuten sein, die man f\u00fcr das Zur\u00fccklegen dieses Weges mit einem bestimmten Fortbewegungsmittel ben\u00f6tigt.<\/p>\n\n\n\n<p>Der Graph ist ein mathematisches Modell, und in der Mathematik k\u00f6nnen Zahlen auch negativ sein. Steht an einer Kante im Graph eine Zahl kleiner als Null, dann sprechen wir demzufolge von einem <em>negativen Kantengewicht<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"beispiel-fuer-negative-kantengewichte\">Beispiel f\u00fcr negative Kantengewichte<\/h3>\n\n\n\n<p>Hier ein Beispiel:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"720\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5.png\" alt=\"Graph mit negativen Kantengewichten\" class=\"wp-image-20083\" style=\"width:600px;height:360px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-224x134.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-336x202.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-504x302.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-672x403.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-400x240.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-600x360.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-800x480.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/graph-with-negative-edge-weights-v5-944x566.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Graph mit negativen Kantengewichten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>In diesem Beispiel hat der Pfad von E nach B ein negatives Kantengewicht von -3, und der Pfad von C nach F hat ein negatives Kantengewicht von -2.<\/p>\n\n\n\n<p>Dieser Graph unterscheidet sich von den vorherigen nicht nur durch die negativen Kantengewichte, sondern auch durch die Pfeile. Diese geben die Richtungen an, in denen man den Pfaden folgen kann.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"gerichtete-kanten-in-einem-gerichteten-graph\">Gerichtete Kanten in einem gerichteten Graph<\/h3>\n\n\n\n<p>Wir sprechen hier von <em>gerichteten Kanten<\/em>. Ein Graph, der gerichtete Kanten enth\u00e4lt, ist ein <em>gerichteter Graph<\/em>.<\/p>\n\n\n\n<p>In einem gerichteten Graphen k\u00f6nnen wir \u2013 im Gegensatz zum ungerichteten Graphen \u2013 auch Pfade darstellen, die nur in einer Richtung verlaufen (z. B. von Knoten A nach B oder von Knoten E nach F) \u2013 sowie Verbindungen, deren Gewicht je nach Richtung unterschiedlich ist (z. B. zwischen Knoten A und D und zwischen C und F).<\/p>\n\n\n\n<p>F\u00fcr beides gibt es naheliegende Anwendungsbeispiele:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Verbindung in nur einer Richtung: Einbahnstra\u00dfen.<\/li>\n\n\n\n<li>Verbindung mit unterschiedlichen Gewichten je Richtung: Stra\u00dfen, die in einer Richtung zweispurig sind und in der anderen einspurig. Oder Autobahnen, auf der in einer Richtung ein Stau herrscht, auf der anderen aber freie Fahrt.<\/li>\n<\/ul>\n\n\n\n<p>Aber <em>negative<\/em> Kantengewichte?<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"wo-kommen-negative-kantengewichte-in-der-praxis-vor\">Wo kommen negative Kantengewichte in der Praxis vor?<\/h3>\n\n\n\n<p>Ein Graph mit negativen Kantengewichten erscheint auf den ersten Blick wie ein realit\u00e4tsfernes, mathematisches Modell. Schlie\u00dflich kann die ben\u00f6tigte Zeit f\u00fcr einen Weg ja nicht negativ sein.<\/p>\n\n\n\n<p>Die Zeit nicht \u2013 aber die Kosten!<\/p>\n\n\n\n<p>Stell dir vor, unser Fahrzeug ist ein Elektroauto. In einem Stra\u00dfennetz mit Steigungen und Gef\u00e4llen soll eine Route von A nach B gefunden werden, auf dem das Fahrzeug am wenigsten Energie verbraucht. <\/p>\n\n\n\n<p>Auf einem Gef\u00e4lle kann das E-Auto seine Batterie aufladen. Und die dabei zur\u00fcckgewonnene Energie k\u00f6nnen wir durch negative Kantengewichte repr\u00e4sentieren.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"warum-sind-dijkstra-und-a-bei-negativen-kantengewichten-nicht-anwendbar\">Warum sind Dijkstra und A* bei negativen Kantengewichten nicht anwendbar?<\/h3>\n\n\n\n<p>Bei <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/dijkstra-algorithmus-java\/\">Dijkstras<\/a> und dem <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/a-stern-algorithmus-java\/\">A*-Algorithmus<\/a> werden die Knoten der Reihe nach abgearbeitet. Wenn ein Knoten abgearbeitet wurde, wird er nicht weiter betrachtet. <\/p>\n\n\n\n<p>Negative Kantengewichte k\u00f6nnten allerdings dazu f\u00fchren, dass die Gesamtkosten vom Start zu einem bereits abgearbeiteten Knoten reduziert werden. Die reduzierten Gesamtkosten w\u00fcrden ignoriert und eine evtl. k\u00fcrzere Route nicht gefunden werden.<\/p>\n\n\n\n<p>Des weiteren: Wenn die Gesamtkosten vom Start zu einem bestimmten Knoten h\u00f6her sind als die einer bereits gefundenen Route zum Ziel, dann betrachten Dijkstra und A* die von diesem Knoten ausgehenden Wege nicht weiter.<\/p>\n\n\n\n<p>Sollte ein solcher Weg ein negatives Kantengewicht haben, w\u00e4re es jedoch m\u00f6glich, dass dieser Weg mit geringeren Gesamtkosten zum Ziel f\u00fchrt (da die Kosten durch das negative Gewicht ja wieder reduziert werden).<\/p>\n\n\n\n<p>Schauen wir uns das am Beispiel von oben an. Es soll die k\u00fcrzeste Route von A nach F gesucht werden.<\/p>\n\n\n\n<p>Dijkstra w\u00fcrde zun\u00e4chst folgende zwei (noch unvollst\u00e4ndige) Wege finden:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A\u2192B\u2192C mit Gesamtkosten vom Start von 4+5 = 9<\/li>\n\n\n\n<li>A\u2192D\u2192E mit Gesamtkosten vom Start von 3+3 = 6<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"744\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01.png\" alt=\"Einsatz von Dijkstras Algorithmus bei negativen Kantengewichten \u2013 vorletzter Schritt\" class=\"wp-image-20075\" style=\"width:600px;height:372px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-224x139.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-336x208.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-504x312.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-672x417.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-400x248.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-600x372.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-800x496.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-01-944x585.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Einsatz von Dijkstras Algorithmus bei negativen Kantengewichten \u2013 vorletzter Schritt<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Dijkstra w\u00fcrde als n\u00e4chstes Knoten E untersuchen (da 6 kleiner ist als 9) und von hier aus einen Weg zu B mit Gesamtkosten von 3+3+(-3) = 3 finden. Dieser Weg ist k\u00fcrzer als der bisher gefundene (4 via A). Da B bereits abgearbeitet ist, w\u00fcrde diese \u00c4nderung wirkungslos sein.<\/p>\n\n\n\n<p>Des weiteren w\u00fcrde Dijkstra einen Weg von E zum Zielknoten F entdecken mit Gesamtkosten von 3+3+2 = 8:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"744\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2.png\" alt=\"Einsatz von Dijkstras Algorithmus bei negativen Kantengewichten \u2013 letzter Schritt\" class=\"wp-image-20126\" style=\"width:600px;height:372px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-224x139.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-336x208.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-504x312.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-672x417.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-400x248.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-600x372.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-800x496.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/pathfinding-with-negative-edge-weights-02-v2-944x585.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Einsatz von Dijkstras Algorithmus bei negativen Kantengewichten \u2013 letzter Schritt<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Da bei Knoten C bereits Gesamtkosten in H\u00f6he von 9 aufgelaufen sind, w\u00fcrde Dijkstra die von C ausgehenden Wege nicht weiter pr\u00fcfen und die Suche beenden.<\/p>\n\n\n\n<p>Was Dijkstra \u00fcbersehen w\u00fcrde: Durch das negative Gewicht von C nach F w\u00fcrden sich die Gesamtkosten des Weges A\u2192B\u2192C\u2192F auf 4+5+(-2) = 7 reduzieren.<\/p>\n\n\n\n<p>Und die Gesamtkosten des Weges A\u2192D\u2192E\u2192B\u2192C\u2192F liegen sogar noch niedriger bei 3+3+(-3)+5+(-2) = 6.<\/p>\n\n\n\n<p>Dijkstras Algorithmus h\u00e4tte bei diesem Beispiel also nicht den k\u00fcrzesten, sondern nur den drittk\u00fcrzesten Weg gefunden.<\/p>\n\n\n\n<p>F\u00fcr den A*-Algorithmus gilt \u00e4hnliches, wobei es bei der Existenz negativer Kantengewichte ohnehin schwer fallen d\u00fcrfte eine sinnvolle Heuristik-Funktion zu definieren.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"wie-funktioniert-der-bellman-ford-algorithmus\">Wie funktioniert der Bellman-Ford-Algorithmus?<\/h2>\n\n\n\n<p>Der Bellman-Ford-Algorithmus \u00e4hnelt dem von Dijkstra stark. Der Unterschied ist, dass wir bei Bellman-Ford die Knoten nicht priorisieren, sondern dass wir in jeder Iteration <em>allen<\/em> Kanten des Graphen folgen und die Gesamtkosten vom Start im Kanten-Zielknoten aktualisieren, wenn diese eine Verbesserung gegen\u00fcber des aktuellen Zustands darstellen.<\/p>\n\n\n\n<p>Ich erkl\u00e4re den Algorithmus in den folgenden Abschnitten am oben vorgestellten Graphen Schritt f\u00fcr Schritt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vorbereitung-tabelle-der-knoten\">Vorbereitung \u2013 Tabelle der Knoten<\/h3>\n\n\n\n<p>Wir beginnen \u2013 genau wie bei Dijkstra \u2013 mit dem Erstellen einer Tabelle aller Knoten mit dem jeweiligen Vorg\u00e4nger-Knoten und den Gesamtkosten vom Startknoten. Die Vorg\u00e4nger-Spalte lassen wir leer, und als Gesamtkosten tragen wir beim Startknoten 0 ein und bei allen anderen Knoten <em>unendlich<\/em> (\u221e):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\">Vorg\u00e4nger<\/th><th class=\"has-text-align-center\" data-align=\"center\">Gesamtkosten<br>vom Start<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">F<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Im folgenden ist es wichtig die Begriffe <em>Kosten<\/em> und <em>Gesamtkosten<\/em> zu differenzieren:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>Kosten<\/em>&nbsp;bezeichnet die Kosten von einem Knoten zu einem Nachbarknoten.<\/li>\n\n\n\n<li><em>Gesamtkosten<\/em>&nbsp;bezeichnet die Summe aller Teilkosten vom Startknoten \u00fcber eventuelle Zwischenknoten zu einem bestimmten Knoten.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bellman-ford-algorithmus-schritt-fuer-schritt\">Bellman-Ford-Algorithmus \u2013 Schritt f\u00fcr Schritt<\/h3>\n\n\n\n<p>Die folgenden Ausschnitte des Graphen zeigen zu jedem Knoten den jeweiligen Vorg\u00e4ngerknoten (wenn vorhanden) und die Gesamtkosten vom Start mit an. Diese Daten sind in der Regel nicht im Graph enthalten, sondern nur in der zuvor angelegten, separaten Tabelle. Ich zeige sie hier der \u00dcbersicht halber mit an.<\/p>\n\n\n\n<p>Wir f\u00fchren nun <em>n-1<\/em> mal (<em>n<\/em> ist die Anzahl der Knoten) die folgende Iteration durch. Wir haben sechs Knoten, also f\u00fcnf Iterationen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Iteration 1 von 5<\/h4>\n\n\n\n<p>In jeder Iteration betrachten wir <em>alle<\/em> Kanten des Graphen. Die Kanten werden mit zwei Kleinbuchstaben in Klammern gekennzeichnet. Die Kante von Knoten A nach B beispielsweise mit <em>(a, b)<\/em>. <\/p>\n\n\n\n<p>Da weder Kanten noch Knoten priorisiert sind, betrachten wir die Kanten in alphabetischer Reihenfolge. Wir beginnen also mit Kante (a, b):<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (a, b)<\/h5>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (a, b)\" class=\"wp-image-20108\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-v4-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (a, b)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen die Summe aus Gesamtkosten vom Start zu A (diese betragen 0, da A selbst der Startknoten ist) und den Kosten der betrachteten Kante (a, b):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (a, b)<\/td><td>&nbsp;&nbsp;&nbsp;0&nbsp;(Gesamtkosten vom Start zu A)<br>+ 4&nbsp;(Kosten A\u2192B)<br>= 4<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Die Gesamtkosten f\u00fcr B sind aktuell noch <em>unendlich<\/em>. Das bedeutet, dass noch keine Route zu B gefunden wurde. Soeben haben wir eine Route entdeckt und tragen daher bei Knoten B als Vorg\u00e4nger den Knoten A ein und als Gesamtkosten vom Start die eben berechnete Summe 4:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten B wurden aktualisiert\" class=\"wp-image-20105\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ab-calced-v2-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger von Knoten B wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h5 class=\"wp-block-heading\">Kante (a, d)<\/h5>\n\n\n\n<p>Wir betrachten als n\u00e4chstes die Kante (a, d):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (a, d)\" class=\"wp-image-20110\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-v3-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (a, d)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen die Gesamtkosten zu D:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (a, d)<\/td><td>&nbsp;&nbsp;&nbsp;0&nbsp;(Gesamtkosten vom Start zu A)<br>+ 3&nbsp;(Kosten A\u2192D)<br>= 3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Da auch die Gesamtkosten bei D noch unendlich sind, tragen wir dort als Gesamtkosten 3 und als Vorg\u00e4nger A ein:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten D wurden aktualisiert\" class=\"wp-image-20111\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ad-calced-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger von Knoten D wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Von Knoten A f\u00fchrt keine weitere Kante weg. Fahren wir mit den Kanten fort, die von Knoten B aus fortf\u00fchren.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (b, c)<\/h5>\n\n\n\n<p>Wir betrachten Kante (b, c):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (b, c)\" class=\"wp-image-20113\" style=\"width:400px;height:92px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-224x52.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-336x77.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-504x116.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-672x155.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-400x92.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-600x138.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (b, c)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen die neue Gesamtkosten f\u00fcr Knoten C:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (b, c)<\/td><td>&nbsp;&nbsp;&nbsp;4&nbsp;(Gesamtkosten vom Start zu B)<br>+ 5&nbsp;(Kosten B\u2192C)<br>= 9<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Auch C hat noch Gesamtkosten von <em>unendlich<\/em>; wir tragen als neue Gesamtkosten bei Knoten C eine 9 ein und als Vorg\u00e4nger Knoten B:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten C wurden aktualisiert\" class=\"wp-image-20114\" style=\"width:400px;height:92px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-224x52.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-336x77.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-504x116.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-672x155.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-400x92.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-600x138.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger von Knoten C wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h5 class=\"wp-block-heading\">Kante (b, e)<\/h5>\n\n\n\n<p>Die n\u00e4chste Kante in alphabetischer Reihenfolge ist Kante (b, e):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"746\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (b, e)\" class=\"wp-image-20117\" style=\"width:400px;height:373px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-224x209.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-336x313.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-504x470.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-672x627.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-400x373.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-600x560.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (b, e)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir rechnen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (b, e)<\/td><td>&nbsp;&nbsp;&nbsp;4&nbsp;(Gesamtkosten vom Start zu B)<br>+ 4&nbsp;(Kosten B\u2192E)<br>= 8<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Und wir aktualisieren Knoten E:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"746\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten E wurden aktualisiert\" class=\"wp-image-20119\" style=\"width:400px;height:373px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced-224x209.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced-336x313.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced-504x470.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced-672x627.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced-400x373.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-be-calced-600x560.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger von Knoten E wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h5 class=\"wp-block-heading\">Kante (c, b)<\/h5>\n\n\n\n<p>Als n\u00e4chstes kommen wir zu Kante (c, b). Dass wir die entgegengesetzte Kante (b, c) bereits betrachtet haben, ist an dieser Stelle irrelevant.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (c, b)\" class=\"wp-image-20114\" style=\"width:400px;height:92px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-224x52.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-336x77.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-504x116.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-672x155.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-400x92.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-bc-calced-600x138.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (c, b)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir sehen nat\u00fcrlich sofort intuitiv, dass es keinen Sinn macht, diesen Weg wieder zur\u00fcckzulaufen. Damit der Algorithmus dies auch sieht, muss er diesen Pfad dennoch \u00fcberpr\u00fcfen. Wir berechnen also die Gesamtkosten f\u00fcr Knoten B, wenn wir diesen \u00fcber die Kante (c, b) erreichen w\u00fcrden:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (c, b)<\/td><td>&nbsp;&nbsp;&nbsp;9&nbsp;(Gesamtkosten vom Start zu C)<br>+ 5&nbsp;(Kosten C\u2192B)<br>= 14<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Wir k\u00f6nnten Knoten B von C aus also mit Gesamtkosten von 14 erreichen. Wir haben aber bereits eine Route zu B mit Gesamtkosten von nur 4 gefunden. Den neu gefundenen Weg ignorieren wir daher und fahren stattdessen mit der n\u00e4chsten Kante fort.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (c, f)<\/h5>\n\n\n\n<p>Wir betrachten die erste Kante mit einem negativen Gewicht, Kante (c, f):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (c, f)\" class=\"wp-image-20134\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (c, f)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen die neuen Gesamtkosten f\u00fcr F:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (c, f)<\/td><td>&nbsp;&nbsp;&nbsp;9&nbsp;(Gesamtkosten vom Start zu C)<br>-  2&nbsp;(Kosten C\u2192F)<br>= 7<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Wir aktualisieren Gesamtkosten und Vorg\u00e4nger in Knoten F:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten F wurden aktualisiert\" class=\"wp-image-20135\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-cf-calced-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger von Knoten F wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir haben die erste Route zum Ziel gefunden. Da es bei Bellman-Ford keine Priorisierung gibt, k\u00f6nnte dieser Weg der k\u00fcrzeste sein, der l\u00e4ngste, oder irgendeiner dazwischen. Wir m\u00fcssen daher mit der Abarbeitung der Kanten fortfahren.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (d, a)<\/h5>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (d, a)\" class=\"wp-image-20169\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-da-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (d, a)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen die Gesamtkosten f\u00fcr A \u00fcber D:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (d, a)<\/td><td>&nbsp;&nbsp;&nbsp;3&nbsp;(Gesamtkosten vom Start zu D)<br>+ 4&nbsp;(Kosten D\u2192A)<br>= 7<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Die neu berechneten Gesamtkosten (7) sind h\u00f6her als die bei A bereits hinterlegten (0). Der Weg \u00fcber D zu A ist also nicht k\u00fcrzer als der bereits bekannte und wird somit nicht weiter beachtet.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (d, e)<\/h5>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (d, e)\" class=\"wp-image-20171\" style=\"width:400px;height:92px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-224x52.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-336x77.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-504x116.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-672x155.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-400x92.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-600x138.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (d, e)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen die Gesamtkosten f\u00fcr E \u00fcber D:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (d, e)<\/td><td>&nbsp;&nbsp;&nbsp;3&nbsp;(Gesamtkosten vom Start zu D)<br>+ 3&nbsp;(Kosten D\u2192E)<br>= 6<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Die neu berechneten Gesamtkosten (6) sind niedriger als die bei Knoten E hinterlegten (8). Wir haben also einen k\u00fcrzeren Weg zu E entdeckt. Wir reduzieren daher die Gesamtkosten in Knoten E von 8 auf 6 und ersetzen Vorg\u00e4nger B durch D:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten E wurden aktualisiert\" class=\"wp-image-20172\" style=\"width:400px;height:92px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced-224x52.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced-336x77.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced-504x116.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced-672x155.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced-400x92.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-de-calced-600x138.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger von Knoten E wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h5 class=\"wp-block-heading\">Kante (e, b)<\/h5>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"746\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (e, b)\" class=\"wp-image-20174\" style=\"width:400px;height:373px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-224x209.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-336x313.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-504x470.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-672x627.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-400x373.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-600x560.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (e, b)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen die Gesamtkosten \u00fcber E zu B:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (e, b)<\/td><td>&nbsp;&nbsp;&nbsp;6&nbsp;(Gesamtkosten vom Start zu E)<br>-  3&nbsp;(Kosten E\u2192B)<br>= 3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Auch hier sind die neu berechneten Gesamtkosten zu B (3) niedriger als die aktuell hinterlegten (4). Wir haben also auch zu B einen k\u00fcrzeren Weg gefunden. Wir aktualisieren Vorg\u00e4nger und Gesamtkosten in Knoten B:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"746\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten B wurden aktualisiert\" class=\"wp-image-20175\" style=\"width:400px;height:373px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced-224x209.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced-336x313.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced-504x470.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced-672x627.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced-400x373.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-eb-calced-600x560.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger von Knoten B wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h5 class=\"wp-block-heading\">Kante (e, f)<\/h5>\n\n\n\n<p>Mit der Kante (e, f) betrachten wir die zweite Kante, die zum Zielknoten F f\u00fchrt:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (e, f)\" class=\"wp-image-20176\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-ef-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (e, f)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (e, f)<\/td><td>&nbsp;&nbsp;&nbsp;6&nbsp;(Gesamtkosten vom Start zu E)<br>+ 2&nbsp;(Kosten E\u2192F)<br>= 8<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Wir haben eine weitere Route zum Zielknoten F \u00fcber Knoten E gefunden. Dieser Weg ist mit Gesamtkosten von 8 jedoch l\u00e4nger als der bisherige (7). Somit ignorieren wir ihn.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (f, c)<\/h5>\n\n\n\n<p>Als letztes betrachten wir die Kante (f, c):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"494\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 1, Kante (f, c)\" class=\"wp-image-20223\" style=\"width:400px;height:247px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc-224x138.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc-336x207.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc-504x311.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc-672x415.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc-400x247.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-1-edge-fc-600x371.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1, Kante (f, c)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (f, c)<\/td><td>&nbsp;&nbsp;&nbsp;7&nbsp;(Gesamtkosten vom Start zu F)<br>+ 4&nbsp;(Kosten F\u2192C)<br>= 11<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Die neu berechneten Gesamtkosten (11) f\u00fcr Knoten C sind niedriger als die hinterlegten (9). Wir ignorieren also auch diese letzte Kante.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Ende der ersten Iteration<\/h5>\n\n\n\n<p>Wir haben nun alle Kanten des Graphen genau einmal betrachtet und eine Route mit Gesamtkosten von 7 zum Ziel gefunden. Mit der Kante (e, b) haben wir allerdings auch die Kosten von Knoten B, dessen ausgehende Kanten wir zuvor schon bearbeitet hatten, noch einmal verringert.<\/p>\n\n\n\n<p>Dies k\u00f6nnte dazu f\u00fchren, dass wir einen noch k\u00fcrzeren Weg zum Ziel finden. Wir wiederholen daher die gesamte Iteration. <\/p>\n\n\n\n<p>Der \u00dcbersicht halber habe ich w\u00e4hrend der ersten Iteration die \u00c4nderungen von Gesamtkosten und Vorg\u00e4ngern direkt im Graphen notiert. Tats\u00e4chlich werden diese \u00c4nderungen in die zuvor angelegte Tabelle eingetragen. Diese sieht am Ende der Iteration wie folgt aus:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\">Vorg\u00e4nger<\/th><th class=\"has-text-align-center\" data-align=\"center\">Gesamtkosten<br>vom Start<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">9<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">6<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">F<\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">7<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Der Graph sieht aktuell so aus:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"746\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph.png\" alt=\"Bellman-Ford-Algorithmus: Gesamtkosten und Vorg\u00e4nger am Ende von Iteration 1\" class=\"wp-image-20178\" style=\"width:600px;height:373px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-224x139.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-336x209.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-504x313.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-672x418.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-400x249.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-600x373.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-800x497.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-graph-944x587.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger am Ende von Iteration 1<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Iteration 2 von 5<\/h4>\n\n\n\n<p>In der zweiten Iteration betrachten wir erneut alle Kanten des Graphen und f\u00fchren die gleichen Berechnungen durch wie in der ersten Iteration. Ich werde die Schritte daher etwas weniger detailreich beschreiben.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kanten (a, b) und (a, d)<\/h5>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (a, b)<\/td><td>&nbsp;&nbsp;&nbsp;0&nbsp;(Gesamtkosten vom Start zu A)<br>+ 4&nbsp;(Kosten A\u2192B)<br>= 4<\/td><\/tr><tr><td>Kante (a, d)<\/td><td>&nbsp;&nbsp;&nbsp;0&nbsp;(Gesamtkosten vom Start zu A)<br>+ 3&nbsp;(Kosten A\u2192D)<br>= 3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Da sich in der vorangegangenen Iteration die Gesamtkosten von Knoten A nicht ge\u00e4ndert haben, sind die Berechnungen f\u00fcr die von Knoten A wegf\u00fchrenden Kanten gleich geblieben. Es ergeben sich keine niedrigeren Gesamtkosten f\u00fcr die Knoten B und D.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (b, c)<\/h5>\n\n\n\n<p>Knoten B ist derjenige, dessen Gesamtkosten wir in der ersten Iteration von 4 auf 3 reduziert haben, <em>nachdem<\/em> wir alle von ihm ausgehenden Kanten bereits betrachtet hatten. Daher schauen wir uns diese Kante noch einmal detailliert an:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 2, Kante (b, c)\" class=\"wp-image-20183\" style=\"width:400px;height:92px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-224x52.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-336x77.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-504x116.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-672x155.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-400x92.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-600x138.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 2, Kante (b, c)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (b, c)<\/td><td>&nbsp;&nbsp;&nbsp;3&nbsp;(Gesamtkosten vom Start zu B)<br>+ 5&nbsp;(Kosten B\u2192C)<br>= 8<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Die neu berechneten Gesamtkosten (8) sind niedriger als die hinterlegten (9). Das war zu erwarten, da wir ja die Gesamtkosten von B um 1 reduziert haben, nachdem wir die Gesamtkosten von C \u00fcber B schon berechnet hatten.<\/p>\n\n\n\n<p>Wir aktualisieren die Gesamtkosten in Knoten C; der Vorg\u00e4nger bleibt unver\u00e4ndert:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"184\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 2: Gesamtkosten von Knoten C wurden aktualisiert\" class=\"wp-image-20184\" style=\"width:400px;height:92px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced-224x52.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced-336x77.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced-504x116.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced-672x155.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced-400x92.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-bc-calced-600x138.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten von Knoten C wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h5 class=\"wp-block-heading\">Kanten (b, e) und (c, b)<\/h5>\n\n\n\n<p>Die n\u00e4chsten zwei Kanten k\u00f6nnen wir wieder im Schnellverfahren abhandeln:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (b, e)<\/td><td>&nbsp;&nbsp;&nbsp;3&nbsp;(Gesamtkosten vom Start zu B)<br>+ 4&nbsp;(Kosten B\u2192E)<br>= 7<\/td><\/tr><tr><td>Kante (c, b)<\/td><td>&nbsp;&nbsp;&nbsp;8&nbsp;(Gesamtkosten vom Start zu C)<br>+ 5&nbsp;(Kosten C\u2192B)<br>= 13<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>In beiden F\u00e4llen ergeben sich f\u00fcr den Kanten-Endknoten h\u00f6here Gesamtkosten als aktuell hinterlegt sind (6 bei E und 3 bei B). Wir haben also keine k\u00fcrzeren Wege gefunden und ignorieren diese zwei Kanten.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Kante (c, f)<\/h5>\n\n\n\n<p>Da wir das Gesamtgewicht von Knoten C eben ver\u00e4ndet haben, betrachten wir auch diese Kante noch einmal genauer:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"496\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 2, Kante (c, f)\" class=\"wp-image-20188\" style=\"width:400px;height:248px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-224x139.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-336x208.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-504x312.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-672x417.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-400x248.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-600x372.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 2, Kante (c, f)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir berechnen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (c, f)<\/td><td>&nbsp;&nbsp;&nbsp;8&nbsp;(Gesamtkosten vom Start zu C)<br>-  2&nbsp;(Kosten C\u2192F)<br>= 6<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Die Gesamtkosten sind niedriger als die hinterlegten. Wir haben also einen k\u00fcrzeren Weg gefunden und aktualisieren die Gesamtkosten in Knoten F von 7 auf 6:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"496\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced.png\" alt=\"Bellman-Ford-Algorithmus, Iteration 2: Gesamtkosten von Knoten F wurden aktualisiert\" class=\"wp-image-20189\" style=\"width:400px;height:248px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced-224x139.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced-336x208.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced-504x312.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced-672x417.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced-400x248.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-2-edge-cf-calced-600x372.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten von Knoten F wurden aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h5 class=\"wp-block-heading\">Kanten (d, a), (d, e), (e, b), (e, f) und (f, c)<\/h5>\n\n\n\n<p>Auch die verbleibenden f\u00fcnf Kanten k\u00f6nnen wir schnell erledigen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter black-borders\"><table><tbody><tr><td>Kante (d, a)<\/td><td>&nbsp;&nbsp;&nbsp;3&nbsp;(Gesamtkosten vom Start zu D)<br>+ 4&nbsp;(Kosten D\u2192A)<br>= 7<\/td><\/tr><tr><td>Kante (d, e)<\/td><td>&nbsp;&nbsp;&nbsp;3&nbsp;(Gesamtkosten vom Start zu D)<br>+ 3&nbsp;(Kosten D\u2192E)<br>= 6<\/td><\/tr><tr><td>Kante (e, b)<\/td><td>&nbsp;&nbsp;&nbsp;6&nbsp;(Gesamtkosten vom Start zu E)<br>-  3&nbsp;(Kosten E\u2192B)<br>= 3<\/td><\/tr><tr><td>Kante (e, f)<\/td><td>&nbsp;&nbsp;&nbsp;6&nbsp;(Gesamtkosten vom Start zu E)<br>+ 2&nbsp;(Kosten E\u2192F)<br>= 8<\/td><\/tr><tr><td>Kante (f, c)<\/td><td>&nbsp;&nbsp;&nbsp;6&nbsp;(Gesamtkosten vom Start zu F)<br>+ 4&nbsp;(Kosten F\u2192C)<br>= 10<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>In allen f\u00fcnf F\u00e4llen sind die neu berechneten Gesamtkosten f\u00fcr den Kanten-Endknoten gr\u00f6\u00dfer oder gleich den aktuellen Werten. Somit gibt es keine weiteren \u00c4nderungen.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\">Ende der zweiten Iteration<\/h5>\n\n\n\n<p>Wir haben nun ein zweites Mal alle Kanten betrachtet. Bei zwei Knoten (C und F) hat dies zur Reduzierung der Gesamtkosten gef\u00fchrt. Und wir haben einen k\u00fcrzeren Weg zum Ziel gefunden als in der ersten Iteration.<\/p>\n\n\n\n<p>Die Tabelle sieht aktuell so aus:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\">Knoten<\/th><th class=\"has-text-align-center\" data-align=\"center\">Vorg\u00e4nger<\/th><th class=\"has-text-align-center\" data-align=\"center\">Gesamtkosten<br>vom Start<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u2013<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">8<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><td class=\"has-text-align-center\" data-align=\"center\">D<\/td><td class=\"has-text-align-center\" data-align=\"center\">6<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">F<\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">6<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Und noch einmal die Gesamtkosten und Vorg\u00e4nger im Graphen:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"744\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph.png\" alt=\"Bellman-Ford-Algorithmus: Gesamtkosten und Vorg\u00e4nger am Ende von Iteration 2\" class=\"wp-image-20191\" style=\"width:600px;height:372px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-224x139.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-336x208.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-504x312.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-672x417.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-400x248.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-600x372.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-800x496.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-iteration-3-graph-944x585.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Gesamtkosten und Vorg\u00e4nger am Ende von Iteration 2<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Um zu pr\u00fcfen, ob wir ein weiteres mal Gesamtkosten reduzieren k\u00f6nnen, f\u00fchren wir eine dritte Iteration durch.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Iteration 3 von 5<\/h4>\n\n\n\n<p>Ich mache es kurz: Nach der dritten Pr\u00fcfung aller Kanten wird der Algorithmus keine weiteren Kostenreduktionen festgestellt haben.<\/p>\n\n\n\n<p>In der Originalvariante w\u00fcrde der Algorithmus noch eine vierte und f\u00fcnfte Iteration durchf\u00fchren. Doch wenn in einer Iteration keine k\u00fcrzeren Wege gefunden werden k\u00f6nnen, dann \u00e4ndert sich die Ausgangssituation nicht f\u00fcr die Folgeiteration. Demzufolge k\u00f6nnen auch in der Folgeiteration (und allen weiteren) keine k\u00fcrzeren Routen mehr gefunden werden.<\/p>\n\n\n\n<p>Eine entsprechend optimierte Variante des Algorithmus wird daher am Ende von Iteration 3 vorzeitig terminieren.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"backtrace-zur-bestimmung-des-vollstaendigen-weges\">Backtrace zur Bestimmung des vollst\u00e4ndigen Weges<\/h3>\n\n\n\n<p>Wir k\u00f6nnen nun aus der Tabelle oder dem Graphen direkt ablesen, dass der k\u00fcrzeste Weg zu F \u00fcber Knoten C f\u00fchrt und dass die Gesamtkosten 6 betragen. Doch wie lautet der vollst\u00e4ndige Pfad?<\/p>\n\n\n\n<p>Diesen ermitteln wir mit Hilfe des sogenannten \"Backtrace\": Wir folgen den Knoten \u2013 Vorg\u00e4nger f\u00fcr Vorg\u00e4nger \u2013 vom Ziel zum Start:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"848\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace.png\" alt=\"Bellman-Ford-Algorithmus: Backtrace zur Bestimmung des vollst\u00e4ndigen Pfades\" class=\"wp-image-20195\" style=\"width:600px;height:424px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-224x158.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-336x237.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-504x356.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-672x475.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-400x283.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-600x424.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-800x565.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-backtrace-944x667.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Backtrace zur Bestimmung des vollst\u00e4ndigen Pfades<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Der Vorg\u00e4nger von F ist C; der Vorg\u00e4nger von C ist B; der Vorg\u00e4nger von B lautet E; der Vorg\u00e4nger von E ist D, und der Vorg\u00e4nger von D ist der Startknoten A. Der gesamte Pfad lautet also: A\u2192D\u2192E\u2192B\u2192C\u2192F<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"kuerzeste-wege-zu-allen-knoten-finden\">K\u00fcrzeste Wege zu <em>allen<\/em> Knoten finden<\/h3>\n\n\n\n<p>Tats\u00e4chlich k\u00f6nnen wir nicht nur den k\u00fcrzesten Pfad zum Zielknoten F ablesen, sondern den k\u00fcrzesten Pfad zu jedem beliebigen Knoten. Im aktuellen Beispiel, in dem der k\u00fcrzeste Pfad \u00fcber <em>alle<\/em> Knoten des Graphen f\u00fchrt, mag das naheliegend sein. Dies gilt jedoch allgemein, da der Algorithmus ja erst dann endet, wenn er im gesamten Graphen keine weitere Kostenreduktion mehr feststellt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"maximale-anzahl-iterationen\">Maximale Anzahl Iterationen<\/h3>\n\n\n\n<p>Zu Beginn des Beispiels habe ich erkl\u00e4rt, dass es maximal <em>n-1<\/em> Iterationen gibt. Warum ist das so?<\/p>\n\n\n\n<p>Der l\u00e4ngstm\u00f6gliche Pfad durch den Graphen f\u00fchrt genau einmal durch alle <em>n<\/em> Knoten, enth\u00e4lt also <em>n-1<\/em> Kanten. Im Worst Case werden in jeder Iteration die Kanten in genau <em>entgegengesetzter<\/em> Richtung zur gesuchten Route gepr\u00fcft. Dies wiederum f\u00fchrt dazu, dass in jeder Iteration die Gesamtkosten nur f\u00fcr <em>eine<\/em> Kante in Richtung Ziel berechnet werden k\u00f6nnen. Bei <em>n-1<\/em> Kanten sind somit <em>n-1<\/em> Iterationen n\u00f6tig. <\/p>\n\n\n\n<p>Am folgende Beispiel ist das gut zu erkennen. Wir suchen in folgendem Graphen den k\u00fcrzesten Weg von A nach D:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"124\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0.png\" alt=\"Bellman-Ford: Worst-Case-Beispiel\" class=\"wp-image-20158\" style=\"width:600px;height:62px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-224x23.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-336x35.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-504x52.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-672x69.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-400x41.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-600x62.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-800x83.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration0-944x98.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Worst-Case-Beispiel<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Iteration 1<\/h4>\n\n\n\n<p>Im schlechtesten Fall besuchen wir die Kanten von rechts nach links, wir beginnen also mit der Kante (c, d). Da die Gesamtkosten von Knoten C noch <em>unendlich<\/em> sind (s. vorheriges Bild), ignorieren wir diese Kante. Gleiches gilt f\u00fcr die Kante (b, c). Erst bei der Kante (a, b) k\u00f6nnen wir die Gesamtkosten f\u00fcr B berechnen (0+2 = 2) und aktualisieren:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"124\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1.png\" alt=\"Bellman-Ford Worst Case, Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten B aktualisiert\" class=\"wp-image-20159\" style=\"width:600px;height:62px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-224x23.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-336x35.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-504x52.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-672x69.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-400x41.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-600x62.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-800x83.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration1-944x98.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Iteration 1: Gesamtkosten und Vorg\u00e4nger von Knoten B aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Iteration 2<\/h4>\n\n\n\n<p>Wieder beginnen wir bei Kante (c, d). Die Gesamtkosten f\u00fcr Knoten C sind nach wie vor nicht berechnet (s. vorheriges Bild), also ignorieren wir die Kante auch in dieser Iteration. Die Gesamtkosten f\u00fcr Knoten B sind berechnet, daher k\u00f6nnen wir anhand der Kante (b, c) jetzt die Gesamtkosten f\u00fcr Knoten C berechnen (2+3 = 5):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"124\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2.png\" alt=\"Bellman-Ford Worst Case, Iteration 2: Gesamtkosten und Vorg\u00e4nger von Knoten C aktualisiert\" class=\"wp-image-20160\" style=\"width:600px;height:62px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-224x23.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-336x35.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-504x52.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-672x69.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-400x41.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-600x62.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-800x83.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration2-944x98.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Iteration 2: Gesamtkosten und Vorg\u00e4nger von Knoten C aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Iteration 3<\/h4>\n\n\n\n<p>Nachdem wir in der zweiten Iteration die Gesamtkosten f\u00fcr Knoten C berechnet haben, k\u00f6nnen wir schlie\u00dflich anhand der Kante (c, d) auch die Gesamtkosten f\u00fcr Knoten D berechnen (5+2 = 7):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"124\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3.png\" alt=\"Bellman-Ford Worst Case, Iteration 3: Gesamtkosten und Vorg\u00e4nger von Knoten D aktualisiert\" class=\"wp-image-20161\" style=\"width:600px;height:62px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-224x23.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-336x35.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-504x52.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-672x69.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-400x41.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-600x62.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-800x83.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-worst-case-iteration3-944x98.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Iteration 3: Gesamtkosten und Vorg\u00e4nger von Knoten D aktualisiert<\/figcaption><\/figure>\n<\/div>\n\n\n<p>F\u00fcr vier Knoten (<em>n = 4<\/em>) haben wir also drei (<em>n - 1<\/em>) Iterationen ben\u00f6tigt.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"identifizierung-negativer-zyklen-in-gerichteten-graphen\">Identifizierung negativer Zyklen in gerichteten Graphen<\/h2>\n\n\n\n<p>Ein Problem, mit dem wir im gezeigten Beispiel nicht konfrontiert wurden, ist das Vorhandensein negativer Zyklen im Graph. Dieser Abschnitt beschreibt, was ein negativer Zyklus ist, warum dieser eine Herausforderung darstellt und wie der Bellman-Ford-Algorithmus diese l\u00f6st.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"was-ist-ein-negativer-zyklus\">Was ist ein negativer Zyklus?<\/h3>\n\n\n\n<p>In einem negativen Zyklus kann man von einem Knoten aus <em>denselben<\/em> Knoten wieder erreichen \u00fcber einen Pfad mit negativen Gesamtkosten. Z. B. in folgendem Graph:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"350\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle.png\" alt=\"Bellman-Ford-Algorithmus: Graph mit negativem Zyklus\" class=\"wp-image-20153\" style=\"width:600px;height:175px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-224x65.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-336x98.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-504x147.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-672x196.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-400x117.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-600x175.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-800x233.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-negative-cycle-944x275.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Graph mit negativem Zyklus<\/figcaption><\/figure>\n\n\n\n<p>In diesem Beispiel hat der zyklische Pfad B\u2192C\u2192D\u2192B Gesamtkosten von 1+2+(-4) = -1<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"warum-ist-ein-negativer-zyklus-problematisch\">Warum ist ein negativer Zyklus problematisch?<\/h3>\n\n\n\n<p>Wir k\u00f6nnen den negativen Zyklus beliebig oft traversieren. Mit jeder Runde reduzieren wir die Gesamtkosten auf allen beteiligten Knoten weiter.<\/p>\n\n\n\n<p>Nehmen wir an, wir suchen im Beispiel oben den Pfad mit den geringsten Gesamtkosten von A nach E. Der naheliegende Weg w\u00e4re A\u2192B\u2192C\u2192D\u2192E mit Gesamtkosten von 5+1+2+3 = 11.<\/p>\n\n\n\n<p>Wir k\u00f6nnten von Knoten D aber auch zur\u00fcck zu B gehen und folgenden Weg zur\u00fccklegen: A\u2192B\u2192C\u2192D\u2192B\u2192C\u2192D\u2192E. Die Gesamtkosten dieses Weges belaufen sich auf 5+1+2+(-4)+1+2+3 = 10. Durch einmaliges Durchlaufen des negativen Zyklus haben wir die Gesamtkosten um 1 reduziert.<\/p>\n\n\n\n<p>Wenn wir dem negativen Zyklus 11 mal durchlaufen, liegen die Gesamtkosten bei 0. Das ist aber nicht das Ende der Fahnenstange. Wir k\u00f6nnen dem negativen Zyklus auch 1.000 mal folgen und die Gesamtkosten auf -989 reduzieren. Oder 1.000.000 mal... es gibt unendlich viele M\u00f6glichkeiten: mit jedem weiteren Durchlauf des negativen Zyklus reduzieren wir die Gesamtkosten weiter.<\/p>\n\n\n\n<p>Der Algorithmus w\u00fcrde also nie enden. Oder er w\u00fcrde, wenn wir ihn nach einer bestimmten Anzahl Iterationen abbrechen, nicht den k\u00fcrzesten Pfad liefern.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"wie-wird-ein-negativer-zyklus-identifiziert\">Wie wird ein negativer Zyklus identifiziert?<\/h3>\n\n\n\n<p>Im Abschnitt <a href=\"#Maximale_Anzahl_Iterationen\">\"Maximale Anzahl Iterationen\"<\/a> habe ich gezeigt, dass Bellman-Ford maximal <em>n-1<\/em> Iterationen durchlaufen muss (<em>n<\/em> ist die Anzahl der Knoten), um den k\u00fcrzesten Weg zu finden.<\/p>\n\n\n\n<p>Der Algorithmus f\u00fchrt nun eine weitere Iteration durch, in der er pr\u00fcft, ob sich an einem <em>beliebigen<\/em> Knoten noch einmal die Gesamtkosten reduzieren w\u00fcrden. Sollte das der Fall sein, ist die Schlussfolgerung, dass es im Graphen einen negativen Zyklus geben muss.<\/p>\n\n\n\n<p>Der Algorithnmus endet dann mit einer entsprechenden Fehlermeldung.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bellman-ford-algorithmus-informelle-beschreibung\">Bellman-Ford-Algorithmus  \u2013 Informelle Beschreibung<\/h2>\n\n\n\n<p>Vorbereitung:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Erstelle eine Tabelle aller Knoten mit Vorg\u00e4ngerknoten und Gesamtkosten vom Start.<\/li>\n\n\n\n<li>Setze die Gesamtkosten des Startknotens auf 0 und die aller anderer Knoten auf&nbsp;<em>unendlich<\/em>.<\/li>\n<\/ol>\n\n\n\n<p>F\u00fchre folgendes <em>n-1<\/em> mal aus (<em>n<\/em> ist die Anzahl der Knoten):<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F\u00fcr jede Kante des Graphen:\n<ol class=\"wp-block-list\">\n<li>Berechne die Summe aus Gesamtkosten zum Kanten-Startknoten und Kantengewicht.<\/li>\n\n\n\n<li>Ist diese Summe niedriger als die aktuellen Gesamtkosten des Kanten-Endknotens, dann setze den Vorg\u00e4nger des Endknotens auf den Kanten-Startknoten und die Gesamtkosten des Endknotens auf die eben berechnete Summe.<\/li>\n<\/ol>\n<\/li>\n\n\n\n<li>Wurden in dieser Iteration keine \u00c4nderungen durchgef\u00fchrt, beende den Algorithmus vorzeitig (in der optimierten Version des Algorithmus).<\/li>\n<\/ul>\n\n\n\n<p>Wenn der Algorithmus nicht vorzeitig beendet wurde, pr\u00fcfe auf negative Zyklen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F\u00fcr jede Kante des Graphen:\n<ol class=\"wp-block-list\">\n<li>Berechne die Summe aus Gesamtkosten zum Kanten-Startknoten und Kantengewicht.<\/li>\n\n\n\n<li>Ist diese Summe niedriger als die aktuellen Gesamtkosten des Kanten-Endknotens, dann beende den Algorithmus mit der Meldung, dass ein negativer Zyklus entdeckt wurde.<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bellman-ford-algorithmus-in-java\">Bellman-Ford-Algorithmus in Java<\/h2>\n\n\n\n<p>Dieser Abschnitt zeigt dir Schritt f\u00fcr Schritt, wie man den Bellman-Ford-Algorithmus in Java implementiert. Den vollst\u00e4ndigen Quellcode findest du in diesem <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/tree\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\" target=\"_blank\">GitHub-Repository, im Paket <code>eu.happycoders.pathfinding.bellman_ford<\/code><\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-fuer-den-graph-guava-valuegraph\">Datenstruktur f\u00fcr den Graph: Guava ValueGraph<\/h3>\n\n\n\n<p>Zun\u00e4chst ben\u00f6tigen wir eine Datenstruktur f\u00fcr den Graph. Diese brauchen wir nicht selbst zu schreiben. Stattdessen verwenden wir den <a rel=\"noopener\" href=\"https:\/\/guava.dev\/releases\/30.0-jre\/api\/docs\/com\/google\/common\/graph\/ValueGraph.html\" target=\"_blank\">ValueGraph<\/a> aus den Google Core Libraries for Java, genauer gesagt den <a rel=\"noopener\" href=\"https:\/\/guava.dev\/releases\/30.0-jre\/api\/docs\/com\/google\/common\/graph\/MutableValueGraph.html\" target=\"_blank\">MutableValueGraph<\/a>. (Die verschiedenen Graph-Klassen werden <a rel=\"noopener\" href=\"https:\/\/github.com\/google\/guava\/wiki\/GraphsExplained\" target=\"_blank\">hier<\/a> erl\u00e4utert.)<\/p>\n\n\n\n<p>Der folgende Code zeigt, wie man den gerichteten Graphen aus dem Artikelbeispiel erstellt (du findest die Methode am Ende der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/TestWithSampleGraph.java\" target=\"_blank\">TestWithSampleGraph<\/a> im GitHub-Repository):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> ValueGraph&lt;String, Integer&gt; <span class=\"hljs-title\">createSampleGraph<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n  MutableValueGraph&lt;String, Integer&gt; graph = ValueGraphBuilder.directed().build();\n  graph.putEdgeValue(<span class=\"hljs-string\">\"A\"<\/span>, <span class=\"hljs-string\">\"B\"<\/span>, <span class=\"hljs-number\">4<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"A\"<\/span>, <span class=\"hljs-string\">\"D\"<\/span>, <span class=\"hljs-number\">3<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"B\"<\/span>, <span class=\"hljs-string\">\"C\"<\/span>, <span class=\"hljs-number\">5<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"B\"<\/span>, <span class=\"hljs-string\">\"E\"<\/span>, <span class=\"hljs-number\">4<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"C\"<\/span>, <span class=\"hljs-string\">\"B\"<\/span>, <span class=\"hljs-number\">5<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"C\"<\/span>, <span class=\"hljs-string\">\"F\"<\/span>, -<span class=\"hljs-number\">2<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"D\"<\/span>, <span class=\"hljs-string\">\"A\"<\/span>, <span class=\"hljs-number\">4<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"D\"<\/span>, <span class=\"hljs-string\">\"E\"<\/span>, <span class=\"hljs-number\">3<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"E\"<\/span>, <span class=\"hljs-string\">\"B\"<\/span>, -<span class=\"hljs-number\">3<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"E\"<\/span>, <span class=\"hljs-string\">\"D\"<\/span>, <span class=\"hljs-number\">3<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"E\"<\/span>, <span class=\"hljs-string\">\"F\"<\/span>, <span class=\"hljs-number\">2<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"F\"<\/span>, <span class=\"hljs-string\">\"C\"<\/span>, <span class=\"hljs-number\">4<\/span>);\n  <span class=\"hljs-keyword\">return<\/span> graph;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Typparameter des&nbsp;<code>ValueGraph<\/code>&nbsp;sind:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Typ der Knoten: im Beispielcode&nbsp;<code>String<\/code>&nbsp;f\u00fcr die Knotennamen \"A\" bis \"F\"<\/li>\n\n\n\n<li>Typ der Kantenwerte: im Beispielcode <code>Integer<\/code>&nbsp;f\u00fcr die Kosten der Kanten<\/li>\n<\/ol>\n\n\n\n<p>Da der Graph gerichtet ist, ist es wichtig, in welcher Reihenfolge die Knoten jeweils angegeben werden. F\u00fcr Kanten, die in beiden Richtungen existieren (z. B. zwischen den Knoten B und C) muss dementsprechend auch zweimal <code>putEdgeValue()<\/code> aufgerufen werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"datenstruktur-fuer-die-knoten-nodewrapper\">Datenstruktur f\u00fcr die Knoten: NodeWrapper<\/h3>\n\n\n\n<p>Als n\u00e4chstes ben\u00f6tigen wir eine Datenstruktur, die f\u00fcr jeden Knoten dessen Gesamtkosten vom Start sowie dessen Vorg\u00e4ngerknoten speichert. Diese Aufgabe erledigt die Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/NodeWrapper.java\" target=\"_blank\">NodeWrapper<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">NodeWrapper<\/span>&lt;<span class=\"hljs-title\">N<\/span>&gt; <\/span>{\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">final<\/span> N node;\n  <span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">int<\/span> totalCostFromStart;\n  <span class=\"hljs-keyword\">private<\/span> NodeWrapper&lt;N&gt; predecessor;\n\n  NodeWrapper(N node, <span class=\"hljs-keyword\">int<\/span> totalCostFromStart, NodeWrapper&lt;N&gt; predecessor) {\n    <span class=\"hljs-keyword\">this<\/span>.node = node;\n    <span class=\"hljs-keyword\">this<\/span>.totalCostFromStart = totalCostFromStart;\n    <span class=\"hljs-keyword\">this<\/span>.predecessor = predecessor;\n  }\n\n  <span class=\"hljs-comment\">\/\/ getter for node<\/span>\n\n  <span class=\"hljs-comment\">\/\/ getters and setters for totalCostFromStart and predecessor <\/span>\n\n  <span class=\"hljs-comment\">\/\/ equals() and hashCode()<\/span>\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Der Typparameter <code>&lt;N&gt;<\/code> steht f\u00fcr den Knotentyp und ist in unserem Beispiel <code>String<\/code> f\u00fcr die Knotennamen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vorbereitung-fuellen-der-tabelle\">Vorbereitung: F\u00fcllen der Tabelle<\/h3>\n\n\n\n<p>Der Algorithmus selbst wird in der Methode <code>findShortestPath(ValueGraph&lt;N, Integer&gt; graph, N source, N target)<\/code> der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/BellmanFord.java\" target=\"_blank\" rel=\"noopener\">BellmanFord<\/a> implementiert.<\/p>\n\n\n\n<p>Als Datenstruktur f\u00fcr die Tabelle verwenden wir eine <code>HashMap<\/code>. Wir iterieren \u00fcber alle Knoten des Graphen, verpacken jeden Knoten in einen <code>NodeWrapper<\/code> und setzen die Gesamtkosten des Startknotens auf 0 und die aller anderen Knoten auf <code>Integer.MAX_VALUE<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\">Map&lt;N, NodeWrapper&lt;N&gt;&gt; nodeWrappers = <span class=\"hljs-keyword\">new<\/span> HashMap&lt;&gt;();\n<span class=\"hljs-keyword\">for<\/span> (N node : graph.nodes()) {\n  <span class=\"hljs-keyword\">int<\/span> initialCostFromStart = node.equals(source) ? <span class=\"hljs-number\">0<\/span> : Integer.MAX_VALUE;\n  NodeWrapper&lt;N&gt; nodeWrapper = <span class=\"hljs-keyword\">new<\/span> NodeWrapper&lt;&gt;(node, initialCostFromStart, <span class=\"hljs-keyword\">null<\/span>);\n  nodeWrappers.put(node, nodeWrapper);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"iterationen\">Iterationen<\/h3>\n\n\n\n<p>Die Logik in den ersten <em>n-1<\/em> Iterationen und die Logik zum Auffinden von negativen Zyklen sind gr\u00f6\u00dftenteils gleich. Daher fasse ich beides in eine Schleife zusammen, die nicht <em>n-1<\/em> mal ausgef\u00fchrt wird, sondern <em>n<\/em> mal:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-comment\">\/\/ Iterate n-1 times + 1 time for the negative cycle detection<\/span>\n<span class=\"hljs-keyword\">int<\/span> n = graph.nodes().size();\n<span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n  <span class=\"hljs-comment\">\/\/ Last iteration for detecting negative cycles?<\/span>\n  <span class=\"hljs-keyword\">boolean<\/span> lastIteration = i == n - <span class=\"hljs-number\">1<\/span>;\n\n  <span class=\"hljs-keyword\">boolean<\/span> atLeastOneChange = <span class=\"hljs-keyword\">false<\/span>;\n\n  <span class=\"hljs-comment\">\/\/ For all edges...<\/span>\n  <span class=\"hljs-keyword\">for<\/span> (EndpointPair&lt;N&gt; edge : graph.edges()) {\n    NodeWrapper&lt;N&gt; edgeSourceWrapper = nodeWrappers.get(edge.source());\n    <span class=\"hljs-keyword\">int<\/span> totalCostToEdgeSource = edgeSourceWrapper.getTotalCostFromStart();\n    <span class=\"hljs-comment\">\/\/ Ignore edge if no path to edge source was found so far<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (totalCostToEdgeSource == Integer.MAX_VALUE) <span class=\"hljs-keyword\">continue<\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Calculate total cost from start via edge source to edge target<\/span>\n    <span class=\"hljs-keyword\">int<\/span> cost = graph.edgeValue(edge).orElseThrow(IllegalStateException::<span class=\"hljs-keyword\">new<\/span>);\n    <span class=\"hljs-keyword\">int<\/span> totalCostToEdgeTarget = totalCostToEdgeSource + cost;\n\n    <span class=\"hljs-comment\">\/\/ Cheaper path found?<\/span>\n    <span class=\"hljs-comment\">\/\/ a) regular iteration --&gt; Update total cost and predecessor<\/span>\n    <span class=\"hljs-comment\">\/\/ b) negative cycle detection --&gt; throw exception<\/span>\n    NodeWrapper edgeTargetWrapper = nodeWrappers.get(edge.target());\n    <span class=\"hljs-keyword\">if<\/span> (totalCostToEdgeTarget &lt; edgeTargetWrapper.getTotalCostFromStart()) {\n      <span class=\"hljs-keyword\">if<\/span> (lastIteration) {\n        <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"Negative cycle detected\"<\/span>);\n      }\n\n      edgeTargetWrapper.setTotalCostFromStart(totalCostToEdgeTarget);\n      edgeTargetWrapper.setPredecessor(edgeSourceWrapper);\n      atLeastOneChange = <span class=\"hljs-keyword\">true<\/span>;\n    }\n  }\n\n  <span class=\"hljs-comment\">\/\/ Optimization: terminate if nothing was changed<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (!atLeastOneChange) <span class=\"hljs-keyword\">break<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Zu Beginn der Schleife pr\u00fcfen wir, ob wir in der letzten Iteration sind.<\/p>\n\n\n\n<p>Dann iterieren wir \u00fcber alle Kanten des Graphen und berechnen die \u00fcber die jeweilige Kante erreichten Gesamtkosten f\u00fcr den Kanten-Endknoten. Sollten diese geringer sein als die bisher gespeicherten, dann aktualisieren wir den Endknoten bzw. \u2013 wenn wir in der letzten Iteration sind \u2013 werfen wir eine Exception aufgrund des erkannten negativen Zyklus.<\/p>\n\n\n\n<p>Zuletzt pr\u00fcfen wir, ob ein Weg zum Ziel gefunden wurde. Wenn ja, rufen wir die Backtrace-Funktion <code>buildPath()<\/code> auf und geben deren Ergebnis zur\u00fcck \u2013 andernfalls ist der R\u00fcckgabewert <code>null<\/code>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-comment\">\/\/ Path found?<\/span>\nNodeWrapper&lt;N&gt; targetNodeWrapper = nodeWrappers.get(target);\n<span class=\"hljs-keyword\">if<\/span> (targetNodeWrapper.getPredecessor() != <span class=\"hljs-keyword\">null<\/span>) {\n  <span class=\"hljs-keyword\">return<\/span> buildPath(targetNodeWrapper);\n} <span class=\"hljs-keyword\">else<\/span> {\n  <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">null<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die vollst\u00e4ndige <code>findShortestPath()<\/code>-Methode findest du in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/BellmanFord.java\" target=\"_blank\">BellmanFord im GitHub-Repository<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"backtrace-methode-in-java\">Backtrace-Methode in Java<\/h3>\n\n\n\n<p>Die Backtrace-Methode <code>buildPath()<\/code> folgt den Knoten Vorg\u00e4nger f\u00fcr Vorg\u00e4nger und tr\u00e4gt diese dabei in eine Liste ein. Schlie\u00dflich wird die Liste in umgekehrter Reihenfolge zur\u00fcckgegeben:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> &lt;N&gt; <span class=\"hljs-function\">List&lt;N&gt; <span class=\"hljs-title\">buildPath<\/span><span class=\"hljs-params\">(NodeWrapper&lt;N&gt; nodeWrapper)<\/span> <\/span>{\n  List&lt;N&gt; path = <span class=\"hljs-keyword\">new<\/span> ArrayList&lt;&gt;();\n  <span class=\"hljs-keyword\">while<\/span> (nodeWrapper != <span class=\"hljs-keyword\">null<\/span>) {\n    path.add(nodeWrapper.getNode());\n    nodeWrapper = nodeWrapper.getPredecessor();\n  }\n  Collections.reverse(path);\n  <span class=\"hljs-keyword\">return<\/span> path;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"aufruf-der-findshortestpath-methode\">Aufruf der findShortestPath()-Methode<\/h3>\n\n\n\n<p>Den Aufruf der <code>findShortestPath()<\/code>-Methode findest du in zwei Beispielen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/TestWithSampleGraph.java\" target=\"_blank\" rel=\"noopener\">TestWithSampleGraph<\/a>: Dieser Test erstellt den Beispiel-Graphen dieses Artikels und sucht darin die k\u00fcrzeste Route von A nach F.<\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/TestWithNegativeCycle.java\">TestWithNegativeCycle<\/a>: Dieser Test erstellt den Beispiel-Graphen aus dem Abschnitt \u00fcber negative Zyklen und sucht darin den k\u00fcrzesten Weg von A nach E.<\/li>\n<\/ul>\n\n\n\n<p>Kommen wir nun zu einem eher theoretischen Thema: der Zeitkomplexit\u00e4t von Bellman-Ford.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-des-bellman-ford-algorithmus\">Zeitkomplexit\u00e4t des Bellman-Ford-Algorithmus<\/h2>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-der-nicht-optimierten-variante\">Zeitkomplexit\u00e4t der nicht optimierten Variante<\/h3>\n\n\n\n<p>Die&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">Zeitkomplexit\u00e4t<\/a>&nbsp;des nicht optimierten Bellman-Ford-Algorithmus ist sehr einfach zu bestimmen.<\/p>\n\n\n\n<p>Aus dem Abschnitt <a href=\"#Maximale_Anzahl_Iterationen\">\"Maximale Anzahl Iterationen\"<\/a> wissen wir bereits, dass der Algorithmus <em>n-1<\/em> Iterationen durchl\u00e4uft, wobei <em>n<\/em> die Anzahl der Knoten ist. In einer weiteren Iteration wird gepr\u00fcft, ob es negative Zyklen gibt.<\/p>\n\n\n\n<p>In jeder Iteration werden alle Kanten des Graphen betrachtet. Wir bezeichnen die Anzahl der Kanten mit <em>m<\/em>.<\/p>\n\n\n\n<p>Der Aufwand f\u00fcr das Behandeln einer Kante ist konstant: <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wir f\u00fchren eine Addition durch und einen Vergleich.<\/li>\n\n\n\n<li>Ggf. \u00e4ndern wir Vorg\u00e4nger und Gesamtkosten des Kanten-Endknotens.<\/li>\n\n\n\n<li>Bei Verwendung einer geeigneten Datenstruktur (z. B. einer <code>HashMap<\/code>) ist das Auffinden des Knoten-Datensatzes in der Tabelle ebenfalls konstant*.<\/li>\n<\/ul>\n\n\n\n<p>Es ergibt sich eine Gesamt-Zeitkomplexit\u00e4t von:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>O(n \u00b7 m)<\/em><\/p>\n\n\n\n<p>F\u00fcr den Sonderfall, dass die Anzahl der Kanten ein Vielfaches der Anzahl der Knoten ist \u2013 in Landau-Notation:&nbsp;<em>m \u2208 O(n)<\/em>&nbsp;\u2013 k\u00f6nnen wir&nbsp;<em>m<\/em>&nbsp;und&nbsp;<em>n<\/em>&nbsp;bei der Berechnung der Zeitkomplexit\u00e4t gleichsetzen.<\/p>\n\n\n\n<p>Aus der Formel wird dann:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>O(n\u00b2)<\/em>&nbsp;f\u00fcr&nbsp;<em>m \u2208 O(n)<\/em><\/p>\n\n\n\n<p>Der Aufwand ist also quadratisch.<\/p>\n\n\n\n<p class=\"hc-footnote has-background\" style=\"background-color:#eeeeee\">* Das ist vereinfacht ausgedr\u00fcckt und gilt bei ausreichender Kapazit\u00e4t der <code>HashMap<\/code> und bei Verwendung einer geeigneten Hash-Funktion. Im Worst Case w\u00fcrde sich der Aufwand f\u00fcr das Auffinden eines Datensatzes auf <em>O(log n)<\/em> verschlechtern (<a href=\"\/de\/algorithmen\/binaere-suche-java\/\">bin\u00e4re Suche<\/a> innerhalb der Buckets). Bei Millionen von Knoten w\u00e4re daher abzuw\u00e4gen, ob man Gesamtkosten und Vorg\u00e4nger direkt in den Knoten hinterlegt anstatt in einer separaten Datenstruktur.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-der-optimierten-variante\">Zeitkomplexit\u00e4t der optimierten Variante<\/h3>\n\n\n\n<p>In der optimierten Variante m\u00fcssen wir best, worst und average case separat betrachten.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Zeitkomplexit\u00e4t der optimierten Variante \u2013 Worst Case<\/h4>\n\n\n\n<p>Bei einem Fall wie im Abschnitt <a href=\"#Maximale_Anzahl_Iterationen\">\"Maximale Anzahl Iterationen\"<\/a> beschrieben kommt die Optimierung nicht zum Tragen, da in <em>jeder<\/em> Iteration \u00c4nderungen erfolgen. Die Zeitkomplexit\u00e4t entspricht somit der des nicht optimierten Algorithmus:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>O(n \u00b7 m)<\/em><\/p>\n\n\n\n<p class=\"has-text-align-center\">bzw. <em>O(n\u00b2)<\/em>&nbsp;f\u00fcr&nbsp;<em>m \u2208 O(n)<\/em><\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Zeitkomplexit\u00e4t der optimierten Variante \u2013 Best Case<\/h4>\n\n\n\n<p>Im Best Case werden nur in der ersten Iteration \u00c4nderungen durchgef\u00fchrt. Die Anzahl der Knoten ist damit f\u00fcr die Zeitkomplexit\u00e4t irrelevant, und der Aufwand w\u00e4chst linear mit der Anzahl der Kanten:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>O(m)<\/em> <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Zeitkomplexit\u00e4t der optimierten Variante \u2013 Average Case<\/h4>\n\n\n\n<p>Im durchschnittlichen Fall reduziert sich die Anzahl der \u00c4nderungen mit jeder Iteration rasch, so dass der Algorithmus nach nur wenigen Iterationen endet. Die Reduktion erfolgt um einen relativ konstanten Faktor, so dass die Anzahl der Iterationen im Average Case in der Gr\u00f6\u00dfenordnung <em>O(log n)<\/em> liegt. Einen formalen Beweis daf\u00fcr konnte ich in der Literatur nicht finden, die Experimente im folgenden Kapitel werden es aber best\u00e4tigen.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t des gesamten Algorithmus wird damit zu:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>O(log n \u00b7 m)<\/em><\/p>\n\n\n\n<p class=\"has-text-align-center\">bzw. <em>O(n \u00b7 log n)<\/em>&nbsp;f\u00fcr&nbsp;<em>m \u2208 O(n)<\/em><\/p>\n\n\n\n<p>Im durchschnittlichen Fall haben wir also quasilinearen Aufwand.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-des-bellman-ford-algorithmus\">Laufzeit des Bellman-Ford-Algorithmus<\/h3>\n\n\n\n<p>Mit dem Tool <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/TestBellmanFordRuntime.java\" target=\"_blank\">TestBellmanFordRuntime<\/a> k\u00f6nnen wir pr\u00fcfen, ob die theoretisch hergeleitete Zeitkomplexit\u00e4t mit der Praxis \u00fcbereinstimmt. Das Programm erstellt Zufallsgraphen verschiedener Gr\u00f6\u00dfen und sucht darin den k\u00fcrzesten Weg zwischen zwei zuf\u00e4llig ausgew\u00e4hlten Knoten.<\/p>\n\n\n\n<p>Die Optimierung des Algorithmus k\u00f6nnen wir f\u00fcr den Test abschalten, indem wir in der <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/bellman_ford\/BellmanFord.java#L69\" target=\"_blank\" rel=\"noopener\">Klasse BellmanFord Zeile 69<\/a> auskommentieren.<\/p>\n\n\n\n<p>Das Tool wiederholt jeden Test 50 mal und gibt anschlie\u00dfend den Median der Messwerte aus. Die folgenden zwei Grafiken zeigen die Messwerte im Verh\u00e4ltnis zur Anzahl der Knoten mit und ohne Optimierung. Da die Messwerte sehr weit auseinanderliegen, habe ich in der ersten Grafik den Fokus auf den Standard-Algorithmus gelegt, in der zweiten Grafik auf den optimierten.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"750\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard.png\" alt=\"Zeitkomplexit\u00e4t des Bellman-Ford-Algorithmus (Ausschnitt: Standardvariante)\" class=\"wp-image-20272\" style=\"width:800px;height:500px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-standard-944x590.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t des Bellman-Ford-Algorithmus (Ausschnitt: Standardvariante)<\/figcaption><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"750\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized.png\" alt=\"Zeitkomplexit\u00e4t des Bellman-Ford-Algorithmus (Ausschnitt: optimierte Variante)\" class=\"wp-image-20273\" style=\"width:800px;height:500px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-time-complexity-optimized-944x590.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t des Bellman-Ford-Algorithmus (Ausschnitt: optimierte Variante)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Sowohl das quadratische Wachstum ohne Optimierung als auch das quasilineare Wachstum mit Optimierung sind gut zu erkennen. Dies entspricht den hergeleiteten Zeitkomplexit\u00e4ten <em>O(n\u00b2)<\/em>&nbsp;f\u00fcr den urspr\u00fcnglichen Algorithmus und <em>O(n \u00b7 log n)<\/em>&nbsp;in der optimierten Variante \u2013 jeweils f\u00fcr&nbsp;<em>m \u2208 O(n)<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"bellman-ford-vs-dijkstra\">Bellman-Ford vs. Dijkstra<\/h3>\n\n\n\n<p>Die folgende Grafik zeigt die Messungen f\u00fcr Bellman-Ford und Dijkstra gegen\u00fcbergestellt (die f\u00fcr Dijkstra haben ich mit dem Tool <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/dijkstra\/TestDijkstraRuntime.java\">TestDijkstraRuntime<\/a> ermittelt):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"750\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra.png\" alt=\"Zeitkomplexit\u00e4t Bellman-Ford-Algorithmus vs. Dijkstra-Algorithmus\" class=\"wp-image-20276\" style=\"width:800px;height:500px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-vs-dijkstra-944x590.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t Bellman-Ford-Algorithmus vs. Dijkstra-Algorithmus<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Es ist gut zu sehen, dass der nicht optimierte Bellman-Ford-Algorithmus um Gr\u00f6\u00dfenordnungen langsamer ist als Dijkstras Algorithmus. Auch der optimierte Bellman-Ford-Algorithmus braucht rund zehnmal l\u00e4nger als Dijkstra (mit Fibonacci Heap).<\/p>\n\n\n\n<p>Sofern wir keine negativen Kantengewichte in unserem Graphen haben, sollten wir also immer Dijkstra oder A* (sofern sich eine Heuristik definieren l\u00e4sst) vorziehen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung-und-ausblick\">Zusammenfassung und Ausblick<\/h2>\n\n\n\n<p>In diesem Artikel hast du gelernt (oder aufgefrischt), was negative Kantengewichte sind, wie der Bellman-Ford-Algorithmus den k\u00fcrzesten Weg in einem gerichteten Graphen mit negativen Kantengewichten findet und wie er negative Zyklen identifiziert.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t der urspr\u00fcnglichen Variante \u2013 sowie die Worst-Case-Zeitkomplexit\u00e4t der optimierten Variante \u2013 ist mit <em>O(n \u00b7 m)<\/em> bzw. <em>O(n\u00b2)<\/em> f\u00fcr <em>m \u2208 O(n)<\/em> deutlich schlechter als die von <a href=\"\/de\/algorithmen\/dijkstra-algorithmus-java\/#Zeitkomplexitat_von_Dijkstras_Algorithmus\">Dijkstra<\/a> und <a href=\"\/de\/algorithmen\/a-stern-algorithmus-java\/#Zeitkomplexitat_des_A-Algorithmus\">A*<\/a>. Dort liegt die Zeitkomplexit\u00e4t beim Einsatz eines Fibonacci-Heaps bei <em>O(n \u00b7 log n + m)<\/em> bzw. <em>O(n \u00b7 log n)<\/em> f\u00fcr <em>m \u2208 O(n)<\/em>.<\/p>\n\n\n\n<p>Im average case schafft die optimierte Variante ebenfalls quasilinearen Aufwand, ist im Experiment aber dennoch etwa zehnmal langsamer als Dijkstra. Bellman-Ford sollte daher nur dann eingesetzt werden, wenn der Graph negative Kantengewichte enth\u00e4lt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vorschau-floyd-warshall-algorithmus\">Vorschau: Floyd-Warshall-Algorithmus<\/h3>\n\n\n\n<p>Im n\u00e4chsten und abschlie\u00dfenden Artikel der Pathfinding-Serie stelle ich den <a href=\"\/de\/algorithmen\/floyd-warshall-algorithmus-java\/\">Floyd-Warshall-Algorithmus<\/a> vor. Dieser wird benutzt, um die k\u00fcrzesten Routen zwischen <em>allen<\/em> Knotenpaaren eines Graphen zu finden (Floyds Variante) \u2013 oder, um festzustellen, zwischen welchen Knotenpaaren es \u00fcberhaupt Routen gibt (Warshalls Variante).<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>Wie funktioniert der Bellman-Ford-Algorithmus und wann setzt man ihn ein? Wo kommen negative Kantengewichte in der Praxis vor? Wie bestimmt man die Zeitkomplexit\u00e4t von Bellman-Ford?<\/p>\n","protected":false},"author":1,"featured_media":43220,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_titles_title":"","_seopress_titles_desc":"Bellman-Ford-Algorithmus \u2013 Schritt f\u00fcr Schritt erkl\u00e4rt. Wo kommen negative Kantengewichte in der Praxis vor? Wie lautet die Zeitkomplexit\u00e4t?","_seopress_robots_index":"","_seopress_robots_follow":"","_seopress_robots_imageindex":"","_seopress_robots_snippet":"","_seopress_robots_primary_cat":"none","_seopress_robots_breadcrumbs":"","_seopress_robots_freeze_modified_date":"","_seopress_robots_custom_modified_date":"","_seopress_robots_canonical":"","_seopress_social_fb_title":"","_seopress_social_fb_desc":"","_seopress_social_fb_img":"","_seopress_social_fb_img_attachment_id":0,"_seopress_social_fb_img_width":0,"_seopress_social_fb_img_height":0,"_seopress_social_twitter_title":"","_seopress_social_twitter_desc":"","_seopress_social_twitter_img":"","_seopress_social_twitter_img_attachment_id":0,"_seopress_social_twitter_img_width":0,"_seopress_social_twitter_img_height":0,"_seopress_redirections_value":"","_seopress_redirections_enabled":"","_seopress_redirections_enabled_regex":"","_seopress_redirections_logged_status":"","_seopress_redirections_param":"","_seopress_redirections_type":301,"_seopress_analysis_target_kw":"bellman-ford,bellman-ford-algorithmus","_seopress_news_disabled":"","_seopress_video_disabled":"","_seopress_video":[],"_seopress_pro_schemas_manual":[{"_seopress_pro_rich_snippets_type":"none"}],"_seopress_pro_rich_snippets_disable_all":"","_seopress_pro_rich_snippets_disable":[],"_seopress_pro_schemas":[],"_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":37613,"_post_count":0,"footnotes":""},"categories":[127],"tags":[137],"class_list":["post-20028","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-algorithmen-pathfinding"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/03\/bellman-ford-algorithm-java-feature-image.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Wie funktioniert der Bellman-Ford-Algorithmus und wann setzt man ihn ein? Wo kommen negative Kantengewichte in der Praxis vor? Wie bestimmt man die Zeitkomplexit\u00e4t von Bellman-Ford?","public_identification_id":"6da7bd753cee4f2ead6bc3120535a9db","private_identification_id":"9fcfb7a26de54d88bca2b30fb81c03c9","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20028","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=20028"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20028\/revisions"}],"predecessor-version":[{"id":52495,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20028\/revisions\/52495"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43220"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=20028"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=20028"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=20028"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}