{"id":20425,"date":"2021-04-12T15:00:00","date_gmt":"2021-04-12T13:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=20425"},"modified":"2025-06-12T09:17:31","modified_gmt":"2025-06-12T07:17:31","slug":"floyd-warshall-algorithmus-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/floyd-warshall-algorithmus-java\/","title":{"rendered":"Floyd-Warshall-Algorithmus (mit Java-Beispiel)"},"content":{"rendered":"\n<p>In dieser Serie \u00fcber Pathfinding-Algorithmen hast du bereits <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/dijkstra-algorithmus-java\/\">Dijkstras Algorithmus<\/a>, den <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/a-stern-algorithmus-java\/\">A*-Algorithmus<\/a> und den <a href=\"\/de\/algorithmen\/bellman-ford-algorithmus-java\/\">Bellman-Ford-Algorithmus<\/a> kennengelernt. In diesem letzten Teil erf\u00e4hrst du, wie der Floyd-Warshall-Algorithmus funktioniert und f\u00fcr welche Zwecke man ihn einsetzt.<\/p>\n\n\n\n<p>Um folgende Themen geht es im einzelnen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Was ist der Einsatzzweck des Floyd-Warshall-Algorithmus?<\/li>\n\n\n\n<li>Wie unterscheidet sich der Floyd-Warshall-Algorithmus von den bisher vorgestellten Pathfinding-Algorithmen?<\/li>\n\n\n\n<li>Wie funktioniert der Floyd-Warshall-Algorithmus (Schritt f\u00fcr Schritt an einem Beispiel erkl\u00e4rt)?<\/li>\n\n\n\n<li>Wie implementiert man den Floyd-Warshall-Algorithmus in Java?<\/li>\n\n\n\n<li>Wie bestimmt man die Zeitkomplexit\u00e4t des Floyd-Warshall-Algorithmus?<\/li>\n<\/ul>\n\n\n\n<p>Den Quellcode der gesamten Artikelserie \u00fcber Pathfinding-Algorithmen findest du <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\" target=\"_blank\">in diesem GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"wann-setzt-man-den-floyd-warshall-algorithmus-ein\">Wann setzt man den Floyd-Warshall-Algorithmus ein?<\/h2>\n\n\n\n<p>Alle bisher vorgestellten Pathfinding-Algorithmen finden den k\u00fcrzesten Weg von <em>einem<\/em> Ausgangsknoten zu einem Zielknoten (oder zu allen anderen Knoten eines Graphen).<\/p>\n\n\n\n<p>Dijkstra priorisiert die Suche dabei nach Gesamtkosten vom Ausgangsknoten. A* priorisiert zus\u00e4tzlich nach gesch\u00e4tzen Kosten bis zum Ziel. Und Bellman-Ford priorisiert gar nicht, kann daf\u00fcr mit negativen Kantengewichten umgehen.<\/p>\n\n\n\n<p>Floyd-Warshall hingegen findet die k\u00fcrzesten Wege zwischen <em>allen<\/em> Paaren von Start- und Zielknoten (Floyds Variante).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"transitive-hulle-eines-graphen\">Transitive H\u00fclle eines Graphen<\/h3>\n\n\n\n<p>Alternativ berechnet Floyd-Warshall die sogenannte \"transitive H\u00fclle\" eines Graphen (Warshalls Variante). Die transitive H\u00fclle erweitert einen Graphen um Kanten zwischen allen <em>indirekt<\/em> verbundenen Knotenpaaren. Wenn der Graph beispielsweise zwei Kanten hat \u2013 eine von A nach B und eine von B nach C \u2013 dann vervollst\u00e4ndigt die transitive H\u00fclle den Graphen um die Kante von A nach C (da ein Weg von A nach C \u00fcber B existiert).<\/p>\n\n\n\n<p>Die folgende Grafik zeigt ein etwas komplexeres Beispiel mit vier Knoten \u2013 links der Ausgangsgraph und rechts dessen transitive H\u00fclle. Die blauen Pfeile stellen die hinzugekommenen, indirekten Verbindungen dar:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1200\" height=\"436\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure.png\" alt=\"Floyd-Warshall-Algorithmus - Transitive H\u00fclle eines Graphen\" class=\"wp-image-20445\" style=\"width:600px;height:218px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-224x81.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-336x122.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-504x183.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-672x244.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-400x145.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-600x218.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-800x291.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-transitive-closure-944x343.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Transitive H\u00fclle eines Graphen<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Beide Aufgabenstellungen sind sehr \u00e4hnlich: Wenn ein k\u00fcrzester Weg zwischen zwei Knotenpaaren existiert, dann geh\u00f6rt dieses Knotenpaar auch in die transitive H\u00fclle \u2013 und vice versa. Daher werden die Varianten von Floyd und Warshall zu einem Algorithmus zusammengefasst.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"wie-funktioniert-der-floyd-warshall-algorithmus\">Wie funktioniert der Floyd-Warshall-Algorithmus?<\/h2>\n\n\n\n<p>Der Algorithmus ist sehr einfach zu implementieren, wie du sp\u00e4ter feststellen wirst. Die Erkl\u00e4rung ist allerdings etwas knifflig. Ich werde den Algorithmus daher zuerst an einem Beispiel beschreiben.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"floyd-warshall-algorithmus-beispiel\">Floyd-Warshall-Algorithmus \u2013 Beispiel<\/h3>\n\n\n\n<p>Der folgende Beispiel-Graph enth\u00e4lt f\u00fcnf Knoten, bezeichnet mit A, B, C, D, E, und verschiedene gerichtete und gewichtete Kanten:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"448\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2.png\" alt=\"Floyd-Warshall-Algorithmus: Beispiel-Graph\" class=\"wp-image-20492\" style=\"width:400px;height:224px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2-224x125.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2-336x188.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2-504x282.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2-672x376.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2-400x224.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-v2-600x336.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Floyd-Warshall-Algorithmus: Beispiel-Graph<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die Zahlen an den Kanten (die Kantengewichte) stellen die Kosten f\u00fcr den jeweiligen Weg dar. Die Kosten von E nach B betragen beispielsweise 4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"vorbereitung-matrix-aller-knotenpaare\">Vorbereitung \u2013 Matrix aller Knotenpaare<\/h3>\n\n\n\n<p>Als Vorbereitung erstellen wir eine <em>n<\/em> \u00d7 <em>n<\/em> gro\u00dfe Matrix (<em>n<\/em> ist die Anzahl der Knoten), in der wir f\u00fcr jedes Knotenpaar (<em>i<\/em>, <em>j<\/em>) das Gewicht der Kante von <em>i<\/em> nach <em>j<\/em> eintragen, falls diese existiert. Ansonsten tragen wir <em>unendlich<\/em> (\u221e) ein. Auf der Diagonalen (die Entfernung eines Knoten zu sich selbst) tragen wir jeweils 0 ein.<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">7<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">4<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Aus der Tabelle k\u00f6nnen wir beispielsweise ablesen: Die Kosten von A nach B betragen 2 (Zeile A, Spalte B).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"floyd-warshall-algorithmus-schritt-fur-schritt\">Floyd-Warshall-Algorithmus \u2013 Schritt f\u00fcr Schritt<\/h3>\n\n\n\n<p>Wir f\u00fchren nun die folgenden f\u00fcnf Iterationen aus. Dabei betrachten wir jeweils einen der Knoten als m\u00f6glichen Zwischenknoten. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"iteration-1-indirekte-wege-uber-zwischenknoten-a\">Iteration 1 \u2013 Indirekte Wege \u00fcber Zwischenknoten A<\/h4>\n\n\n\n<p>Wir vergleichen f\u00fcr alle Knotenpaare (<em>i<\/em>, <em>j<\/em>) die eingetragenen Kosten des direkten Weges mit den Kosten des indirekten Weges von <em>i<\/em> nach <em>j<\/em> \u00fcber Knoten A \u2013 also die Kosten von Knoten <em>i<\/em> nach Knoten A plus der Kosten von Knoten A nach Knoten <em>j<\/em> (sofern solch ein Weg existiert). Sind die Kosten \u00fcber Zwischenknoten A geringer als die bisherigen, ersetzen wir die Kosten in der Matrix.<\/p>\n\n\n\n<p>Knotenpaare, bei denen <em>i<\/em> = <em>j<\/em> ist oder <em>i<\/em> = A oder <em>j<\/em> = A k\u00f6nnen wir \u00fcberspringen. Die Entfernung eines Knotens zu sich selbst ist immer 0. Und wenn Start oder Ziel bereits A sind, gibt es nicht auch noch einen indirekten Weg \u00fcber A.<\/p>\n\n\n\n<p>Wir beginnen somit mit dem Knotenpaar (B, C). Die Kosten des direkten Weges sind 6 (abzulesen in Zeile B, Spalte C). Von B nach A ist aktuell kein Weg bekannt (in Zeile B, Spalte A steht <em>unendlich<\/em>). Wir k\u00f6nnen also in diesem Schritt keinen k\u00fcrzeren Weg \u00fcber A finden. Dementsprechend k\u00f6nnen wir auch keine k\u00fcrzeren Wege f\u00fcr (B, D) und (B, E) via A finden.<\/p>\n\n\n\n<p>Auch von C und D gibt es aktuell keine bekannten Wege zu Knoten A (Zeilen C und D, jeweils Spalte A enth\u00e4lt <em>unendlich<\/em>). Wir k\u00f6nnen somit f\u00fcr (C, B), (C, D), (C, E), (D, B), (D, C), (D, E) aktuell keine k\u00fcrzeren Wege finden.<\/p>\n\n\n\n<p>Beim Knotenpaar (E, B) beginnt es interessant zu werden. Die aktuellen Kosten des direkten Weges E\u2192B betragen 4. Gibt es einen k\u00fcrzeren Weg \u00fcber Knoten A? Hier noch mal der entsprechende Ausschnitt des Graphen:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"448\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a.png\" alt=\"Floyd-Warshall-Algorithmus: Iteration 1: Vergleich Pfad E\u2192B mit E\u2192A\u2192B\" class=\"wp-image-20493\" style=\"width:400px;height:224px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a-224x125.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a-336x188.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a-504x282.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a-672x376.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a-400x224.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1a-600x336.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1: Vergleich Pfad E\u2192B mit E\u2192A\u2192B<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die Kosten von E nach A betragen 1 (in der Tabelle Zeile E, Spalte A); die Kosten von A nach B betragen 2 (Zeile A, Spalte B). In Summe ergibt das 3. Die Kosten des indirekten Weges von E nach B \u00fcber Knoten A sind also geringer als die des direkten Weges. Wir haben also folgenden, k\u00fcrzeren Weg gefunden:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"500\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b.png\" alt=\"Floyd-Warshall-Algorithmus: Iteration 1: Pfad E\u2192B\u2192A ist k\u00fcrzer als E\u2192B\" class=\"wp-image-20494\" style=\"width:400px;height:250px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step1b-600x375.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 1: Pfad E\u2192B\u2192A ist k\u00fcrzer als E\u2192B<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir ersetzen daher in Zeile E, Spalte B die 4 durch eine 3 (in der Tabelle fett hervorgehoben):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">2<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">6<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">7<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><td class=\"has-text-align-center\" data-align=\"center\">3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">1<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong><span class=\"has-inline-color has-black-color\">3<\/span><\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">\u221e<\/td><td class=\"has-text-align-center\" data-align=\"center\">0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Wir betrachten als n\u00e4chsten Knotenpaar (E, C). Die aktuellen Kosten betragen <em>unendlich<\/em>, da noch kein Weg gefunden wurde. Gibt es einen indirekten Weg \u00fcber A, also E\u2192A\u2192C? Da aktuell kein Weg von A nach C bekannt ist (Zeile A, Spalte C enth\u00e4lt <em>unendlich<\/em>), ist die Antwort \"nein\".<\/p>\n\n\n\n<p>Zuletzt schauen wir auf das Knotenpaar (E, D). Da auch von A nach D aktuell kein Weg bekannt ist, finden wir in diesem Schritt auch keinen indirekten Weg E\u2192A\u2192D.<\/p>\n\n\n\n<p>Wir haben alle Knotenpaare betrachtet; Schritt 1 ist damit beendet. Wir kennen jetzt f\u00fcr alle Knotenpaare die niedrigsten Kosten, wenn wir auch indirekte Wege \u00fcber Zwischenknoten A zulassen. Insbesondere haben wir in diesem Schritt einen k\u00fcrzeren Weg von E nach B via Knoten A gefunden.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"iteration-2-indirekte-wege-uber-zwischenknoten-b\">Iteration 2 \u2013 Indirekte Wege \u00fcber Zwischenknoten B<\/h4>\n\n\n\n<p>In der zweiten Iteration vergleichen wir f\u00fcr alle Knotenpaare (<em>i<\/em>, <em>j<\/em>) wiederum die eingetragenen Kosten (dies sind nun entweder die Kosten des direkten Weges oder die \u00fcber Zwischenknoten A \u2013 je nachdem welche geringer sind) mit den Kosten von <em>i<\/em> nach <em>j<\/em> \u00fcber Knoten B.<\/p>\n\n\n\n<p>Die Kosten zu und von Knoten B lesen wir aus der Matrix ab. Das hei\u00dft, dass dies nicht unbedingt die Kosten des direkten Weges zu\/von Knoten B sein m\u00fcssen. Es k\u00f6nnten auch die in Schritt 1 bestimmten, niedrigeren Kosten via Zwischenknoten A sein (z. B. von E nach B: 3 via A anstatt 4 direkt).<\/p>\n\n\n\n<p>Wir beginnen mit Knotenpaar (A, C). Bisher wurde noch kein Weg gefunden (Zeile A, Spalte C enth\u00e4lt <em>unendlich<\/em>). Schauen wir uns den indirekten Weg \u00fcber B an:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"500\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a.png\" alt=\"Floyd-Warshall-Algorithmus: Iteration 2: von A nach C \u00fcber B\" class=\"wp-image-20496\" style=\"width:400px;height:250px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2a-600x375.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 2: von A nach C \u00fcber B<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die Kosten von A nach B betragen 2, und die Kosten von B nach C betragen 6. Die Summe ist 8. Das ist auf jeden Fall besser als gar kein Weg. Wir tragen daher in Zeile A, Spalte C die 8 ein:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td><strong>A<\/strong><\/td><td><strong>B<\/strong><\/td><td><strong>C<\/strong><\/td><td><strong>D<\/strong><\/td><td><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td>0<\/td><td>2<\/td><td><strong>8<\/strong><\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td>\u221e<\/td><td>0<\/td><td>6<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td>\u221e<\/td><td>7<\/td><td>0<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td>\u221e<\/td><td>\u221e<\/td><td>1<\/td><td>0<\/td><td>3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td>1<\/td><td>3<\/td><td>\u221e<\/td><td>\u221e<\/td><td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Weiter geht es mit Knotenpaar (A, D). Auch hier ist bisher kein Weg bekannt. Gibt es einen Weg \u00fcber Zwischenknoten B? Die Kosten von A nach B hatten wir eben bereits als 2 abgelesen. Von B nach D allerdings ist bisher kein Weg bekannt. Somit k\u00f6nnen wir auch keine Kosten f\u00fcr den Weg A\u2192B\u2192D bestimmen, und der Eintrag f\u00fcr Knotenpaar (A, D) bleibt unver\u00e4ndert (<em>unendlich<\/em>).<\/p>\n\n\n\n<p>Genauso ergeht es uns mit Knotenpaar (A, E): Es gibt zwar nach wie vor den Weg A\u2192B, aber keinen Weg B\u2192E, somit auch keinen Weg A\u2192B\u2192E und damit keinen neuen Eintrag f\u00fcr Knotenpaar (A, E).<\/p>\n\n\n\n<p>Wir kommen zu den Knotenpaaren (C, A), (C, D) und (C, E): Aktuell ist f\u00fcr alle drei Paare kein Weg bekannt. Es gibt einen Weg C\u2192B mit Kosten von 7, aber von Zwischenknoten B weder einen Weg zu A, zu D oder zu E, somit also auch keine Wege C\u2192B\u2192A, C\u2192B\u2192D oder C\u2192B\u2192E. Die Eintr\u00e4ge f\u00fcr die drei Knotenpaare bleiben daher unver\u00e4ndert (<em>unendlich<\/em>).  <\/p>\n\n\n\n<p>Knotenpaare (D, A), (D, C) und (D, E): Da es keinen Weg von Knoten D zu Zwischenknoten B gibt, k\u00f6nnen wir auch f\u00fcr diese drei Knotenpaare keine (oder keine k\u00fcrzeren) Wege finden.<\/p>\n\n\n\n<p>Knotenpaar (E, A): Es gibt zwar einen Weg von E nach B, aber keinen Weg von B nach A, somit auch keinen Weg E\u2192B\u2192A.<\/p>\n\n\n\n<p>Bei Knotenpaar (E, C) kommt wieder etwas Schwung rein: Aktuell ist kein Weg bekannt. Gibt es einen Weg \u00fcber B? Es gibt einen Weg E\u2192B mit Kosten von 3 und einen Weg B\u2192C mit Kosten von 6. Somit existiert ein Weg von E \u00fcber B nach C mit Gesamtkosten von 9. Wir tragen die 9 in Zeile E, Spalte C ein:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td><strong>A<\/strong><\/td><td><strong>B<\/strong><\/td><td><strong>C<\/strong><\/td><td><strong>D<\/strong><\/td><td><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td>0<\/td><td>2<\/td><td>8<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td>\u221e<\/td><td>0<\/td><td>6<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td>\u221e<\/td><td>7<\/td><td>0<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td>\u221e<\/td><td>\u221e<\/td><td>1<\/td><td>0<\/td><td>3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td>1<\/td><td>3<\/td><td><strong>9<\/strong><\/td><td>\u221e<\/td><td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Beachte, dass dies nicht hei\u00dft, dass der Weg von E nach C nur \u00fcber Knoten B gehen muss. Denn der Weg von E nach B mit den Kosten 3 geht auch noch \u00fcber den Knoten A (diesen hatten wir in Schritt 1 gefunden). Genau genommen haben wir jetzt also den Weg E\u2192A\u2192B\u2192C gefunden:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"576\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b.png\" alt=\"Floyd-Warshall-Algorithmus: Iteration 2: von E nach C \u00fcber B (und damit auch \u00fcber A)\" class=\"wp-image-20499\" style=\"width:400px;height:288px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b-224x161.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b-336x242.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b-504x363.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b-672x484.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b-400x288.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step2b-600x432.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 2: von E nach C \u00fcber B (und damit auch \u00fcber A)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Betrachten wir das letzte Knotenpaar in dieser Iteration, (E, D). Existiert ein Weg \u00fcber Zwischenknoten B? Es existiert zwar ein Weg E\u2192B mit Kosten 3, allerdings kein Weg B\u2192D, somit also auch kein Weg E\u2192B\u2192D.<\/p>\n\n\n\n<p>Die zweite Iteration ist beendet. Wir kennen nun f\u00fcr alle Knotenpaare die niedrigsten Kosten, wenn wir auch indirekte Wege \u00fcber Knoten B \u2013 und damit auch indirekt \u00fcber Knoten A \u2013 zulassen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"iteration-3-indirekte-wege-uber-zwischenknoten-c\">Iteration 3 \u2013 Indirekte Wege \u00fcber Zwischenknoten C<\/h4>\n\n\n\n<p>Wir wiederholen das ganze: Jetzt vergleichen wir f\u00fcr alle Knotenpaare die eingetragenen Kosten mit denen \u00fcber Zwischenknoten C. Die Kosten zu\/von Knoten C, die wir wiederum aus der Matrix ablesen, k\u00f6nnen die des direkten Weges zu\/von Knoten C sein, aber auch die in den vorherigen Iterationen bestimmten Kosten von indirekten Wegen via Knoten A und\/oder B.<\/p>\n\n\n\n<p>Wir beginnen mit Knotenpaar (A, B). Die Kosten von A nach Zwischenknoten C betragen 8 (diesen Weg hatten wir am Anfang der zweiten Iteration via B gefunden). Die Kosten von C nach B betragen 7. Der Weg \u00fcber Zwischenknoten C hat also Gesamtkosten von 8 + 7 = 15. Dieser Weg ist deutlich l\u00e4nger als der aktuell hinterlegte mit Kosten von 2. Das ist in der Grafik auch gut zu erkennen: Der Weg A\u2192B ist nat\u00fcrlich deutlich k\u00fcrzer als A\u2192B\u2192C\u2192B. Wir belassen den Eintrag f\u00fcr (A, B) also auf 2.<\/p>\n\n\n\n<p>Knotenpaare (A, D) und (A, E): Die Kosten f\u00fcr A\u2192C haben wir gerade abgelesen, es existieren allerdings keine Wege C\u2192D bzw. C\u2192E, somit also auch keine von A via C nach D bzw. von A via C nach E.<\/p>\n\n\n\n<p>Knotenpaar (B, A), (B, D), (B, E): Die Kosten von B nach C betragen 6, von C existiert allerdings weder ein Pfad zu A, zu D oder zu E. Somit finden wir in dieser Iteration auch keinen der Wege B\u2192C\u2192A, B\u2192C\u2192D und B\u2192C\u2192E.<\/p>\n\n\n\n<p>Knotenpaar (D, A): Es existiert ein Pfad von D nach C, allerdings keiner von C nach A, somit auch keiner von D via C nach A.<\/p>\n\n\n\n<p>F\u00fcr Knotenpaar (D, B) ist aktuell als Kosten <em>unendlich<\/em> hinterlegt, d. h. es ist noch kein Pfad bekannt. Das \u00e4ndert sich jetzt: Es existiert der Pfad D\u2192C mit Kosten 1 und der Pfad C\u2192B mit Kosten 7. In Summe ergibt das 8:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"454\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3.png\" alt=\"Floyd-Warshall-Algorithmus: Iteration 3: von D nach B \u00fcber C\" class=\"wp-image-20503\" style=\"width:400px;height:227px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3-224x127.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3-336x191.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3-504x286.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3-672x381.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3-400x227.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step3-600x341.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 3: von D nach B \u00fcber C<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir tragen somit in Zeile D, Spalte B die 8 ein:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td><strong>A<\/strong><\/td><td><strong>B<\/strong><\/td><td><strong>C<\/strong><\/td><td><strong>D<\/strong><\/td><td><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td>0<\/td><td>2<\/td><td>8<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td>\u221e<\/td><td>0<\/td><td>6<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td>\u221e<\/td><td>7<\/td><td>0<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td>\u221e<\/td><td><strong>8<\/strong><\/td><td>1<\/td><td>0<\/td><td>3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td>1<\/td><td>3<\/td><td>9<\/td><td>\u221e<\/td><td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Knotenpaar (D, E): Es ist kein Weg von Zwischenknoten C nach E bekannt, somit finden wir in dieser Iteration auch keinen Weg von D via C nach E.<\/p>\n\n\n\n<p>Knotenpaare (E, A) und (E, D): Da keine Wege von Zwischenknoten C nach A bzw. nach D existieren, finden wir aktuell auch keinen Weg von E via C nach A bzw. von E via C nach D.<\/p>\n\n\n\n<p>Knotenpaar (E, B): Die Kosten f\u00fcr den Weg E\u2192C betragen 9, die Kosten f\u00fcr C\u2192B betragen 7. In Summe also 16. F\u00fcr den Weg E\u2192B sind bereits Kosten von 3 hinterlegt. 16 ist deutlich schlechter, wir lassen also die 3 unver\u00e4ndert stehen.<\/p>\n\n\n\n<p>Am Ende von Iteration 3 angekommen kennen wir die niedrigsten Kosten f\u00fcr alle Knotenpaare, wenn wir auch indirekte Wege \u00fcber Knoten C \u2013 und damit auch \u00fcber A und B \u2013 zulassen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"iteration-4-indirekte-wege-uber-zwischenknoten-d\">Iteration 4 \u2013 Indirekte Wege \u00fcber Zwischenknoten D<\/h4>\n\n\n\n<p>Iteration 4 k\u00f6nnen wir abk\u00fcrzen: Von keinem der Knoten gibt es einen Weg <em>zu<\/em> Zwischenknoten D. Somit werden wir f\u00fcr kein Knotenpaar einen Weg via D finden. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"iteration-5-indirekte-wege-uber-zwischenknoten-e\">Iteration 5 \u2013 Indirekte Wege \u00fcber Zwischenknoten E<\/h4>\n\n\n\n<p>In der letzten Iteration pr\u00fcfen wir f\u00fcr alle Knotenpaare, ob wir einen k\u00fcrzeren Weg \u00fcber Zwischenknoten E finden.<\/p>\n\n\n\n<p>Die Knotenpaare mit Startknoten A, B und C k\u00f6nnen wir schnell abhandeln: Von keinem dieser Knoten existiert ein Weg zu Zwischenknoten E, somit werden wir f\u00fcr keines dieser Knotenpaare einen Weg via E finden.<\/p>\n\n\n\n<p>Knotenpaar (D, A): Die Kosten f\u00fcr den Pfad D\u2192E betragen 3, die Kosten f\u00fcr E\u2192A betragen 1. Es existiert also ein Weg von D via E nach A mit Gesamtkosten von 4:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"448\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a.png\" alt=\"Floyd-Warshall-Algorithmus: Iteration 5: von D nach A via E\" class=\"wp-image-20507\" style=\"width:400px;height:224px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a-224x125.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a-336x188.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a-504x282.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a-672x376.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a-400x224.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5a-600x336.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 5: von D nach A via E<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir tragen die 4 in Zeile D, Spalte A ein:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td><strong>A<\/strong><\/td><td><strong>B<\/strong><\/td><td><strong>C<\/strong><\/td><td><strong>D<\/strong><\/td><td><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td>0<\/td><td>2<\/td><td>8<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td>\u221e<\/td><td>0<\/td><td>6<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td>\u221e<\/td><td>7<\/td><td>0<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td><strong>4<\/strong><\/td><td>8<\/td><td>1<\/td><td>0<\/td><td>3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td>1<\/td><td>3<\/td><td>9<\/td><td>\u221e<\/td><td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Knotenpaar (D, B): Die Kosten f\u00fcr den Pfad D\u2192E betragen weiterhin 3, die Kosten f\u00fcr E\u2192B betragen ebenfalls 3. Ergibt in Summe 6. Wir haben also einen Weg von D via E nach B gefunden mit Gesamtkosten von 6. Aktuell sind hier Gesamtkosten von 8 eingetragen. Wir ersetzen die 8 durch 6:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td><strong>A<\/strong><\/td><td><strong>B<\/strong><\/td><td><strong>C<\/strong><\/td><td><strong>D<\/strong><\/td><td><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td>0<\/td><td>2<\/td><td>8<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td>\u221e<\/td><td>0<\/td><td>6<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td>\u221e<\/td><td>7<\/td><td>0<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td>4<\/td><td><strong>6<\/strong><\/td><td>1<\/td><td>0<\/td><td>3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td>1<\/td><td>3<\/td><td>9<\/td><td>\u221e<\/td><td>0<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Auch dieser Fall ist wieder ein Beispiel daf\u00fcr, dass der Weg via Zwischenknoten E nicht der direkte Weg D\u2192E\u2192B ist, sondern tats\u00e4chlich D\u2192E\u2192A\u2192B, da der k\u00fcrzeste Weg von E nach B \u00fcber A geht (den Weg E\u2192A\u2192B hatten wir in der ersten Iteration gefunden):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"506\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b.png\" alt=\"Floyd-Warshall-Algorithmus: Iteration 5: von D nach B via E (und A)\" class=\"wp-image-20509\" style=\"width:400px;height:253px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-224x142.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-336x213.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-504x319.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-672x425.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-400x253.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-600x380.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Iteration 5: von D nach B via E (und A)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Das finale Knotenpaar ist (D, C): Die Kosten f\u00fcr den Pfad D\u2192E betragen immer noch 3, die Kosten f\u00fcr E\u2192C betragen 9. Ergibt in Summe 12. Dies ist schlechter als die f\u00fcr (D, C) aktuell hinterlegten Kosten von 1, die wir somit stehen lassen.<\/p>\n\n\n\n<p>Wir haben das Ende der f\u00fcnften Iteration erreicht und kennen nun die niedrigsten Kosten f\u00fcr alle Knotenpaare, wenn wir auch indirekte Wege \u00fcber Knoten E (und damit auch \u00fcber A, B, C, D) \u2013 also \u00fcber beliebige anderen Knoten \u2013 zulassen. <\/p>\n\n\n\n<p>Das Ziel des Algorithmus ist damit erreicht.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"erkennung-negativer-zyklen-im-graphen\">Erkennung negativer Zyklen im Graphen<\/h2>\n\n\n\n<p>Was ist ein negativer Zyklus? Und warum stellt dieser ein Problem dar? Diese Fragen habe ich im Artikel \u00fcber den Bellman-Ford-Algorithmus beantwortet. <a href=\"\/de\/algorithmen\/bellman-ford-algorithmus-java\/#Identifizierung_negativer_Zyklen_in_gerichteten_Graphen\">Dieser Link f\u00fchrt direkt zu dem entsprechenden Abschnitt<\/a>.<\/p>\n\n\n\n<p>Ein negativer Zyklus von einem beliebigen Knoten aus f\u00fchrt dazu, dass die Kosten von diesem Knoten <em>zu sich selbst<\/em> negativ sind. Der Floyd-Warshall-Algorithmus macht es uns sehr leicht das zu erkennen. Die Kosten aller Knoten zu sich selbst lassen sich an der Matrix-Diagonalen direkt ablesen. Hier noch einmal die Matrix aus dem Beispiel von oben nach Durchlauf aller Iterationen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td><strong>A<\/strong><\/td><td><strong>B<\/strong><\/td><td><strong>C<\/strong><\/td><td><strong>D<\/strong><\/td><td><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td><strong>0<\/strong><\/td><td>2<\/td><td>8<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td>\u221e<\/td><td><strong>0<\/strong><\/td><td>6<\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td>\u221e<\/td><td>7<\/td><td><strong>0<\/strong><\/td><td>\u221e<\/td><td>\u221e<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td>4<\/td><td>6<\/td><td>1<\/td><td><strong>0<\/strong><\/td><td>3<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td>1<\/td><td>3<\/td><td>9<\/td><td>\u221e<\/td><td><strong>0<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>In der Diagonalen (fett hervorgehoben) befinden sich ausschlie\u00dflich Nullen. Das hei\u00dft: Es existiert <em>kein<\/em> negativer Zyklus. <\/p>\n\n\n\n<p>Sollte sich in wenigstens einem Feld auf der Diagonalen eine negative Zahl befinden, w\u00e4re ein negativer Zyklus erkannt. Der Algorithmus w\u00fcrde dann mit einer Fehlermeldung terminieren.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"floyd-warshall-algorithmus-bestimmung-der-kuerzesten-pfade\">Floyd-Warshall-Algorithmus \u2013 Bestimmung der k\u00fcrzesten Pfade<\/h2>\n\n\n\n<p>In der oben beschriebenen Grundform berechnet der Floyd-Warshall-Algorithmus nur die <em>Kosten<\/em> der k\u00fcrzesten Pfade zwischen zwei Knoten, nicht jedoch die Pfade selbst (d. h. \u00fcber welche Zwischenknoten der k\u00fcrzeste Pfad f\u00fchrt).<\/p>\n\n\n\n<p>Man kann den Algorithmus jedoch relativ einfach erweitern, so dass die Bestimmung des k\u00fcrzesten Pfades zwischen zwei Knoten leicht m\u00f6glich ist.<\/p>\n\n\n\n<p>Dazu ben\u00f6tigen wir eine zweite Matrix der Gr\u00f6\u00dfe <em>n<\/em> \u00d7 <em>n<\/em>, die sogenannte \"Nachfolgermatrix\". Hier tragen wir f\u00fcr jedes Knotenpaar (<em>i<\/em>, <em>j<\/em>) initial den jeweiligen Endknoten <em>j<\/em> ein. Das bedeutet, dass der Weg von <em>i<\/em> nach <em>j<\/em> initial \u00fcber den Nachfolger <em>j<\/em> f\u00fchrt.<\/p>\n\n\n\n<p>Sobald wir f\u00fcr ein beliebiges Paar (<em>i<\/em>, <em>j<\/em>) einen k\u00fcrzeren Weg \u00fcber Zwischenknoten <em>k<\/em> finden, tragen wir in der Matrix an Position (<em>i<\/em>, <em>j<\/em>) den aktuellen Wert der Matrix von Position (<em>i<\/em>, <em>k<\/em>) ein. Das bedeutet, dass der Weg von <em>i<\/em> nach <em>j<\/em> nun \u00fcber denselben Nachfolger f\u00fchrt wie der Weg von <em>i<\/em> nach <em>k<\/em>. Der Nachfolger kann <em>k<\/em> selbst sein, aber auch ein weiterer Zwischenknoten auf dem k\u00fcrzesten Weg zu <em>k<\/em>. <\/p>\n\n\n\n<p>Im Beispiel oben w\u00fcrden wir die Nachfolgermatrix initial wie folgt bef\u00fcllen:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>A<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"> -<\/td><td class=\"has-text-align-left\" data-align=\"left\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">- <\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-left\" data-align=\"left\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>In Iteration 1 finden wir von E nach B einen k\u00fcrzeren Weg \u00fcber A. Der Nachfolger von E auf dem Weg zu A (Zeile E, Spalte A) ist A; somit tragen wir A auch als Nachfolger von E auf dem Weg nach B (Zeile E, Spalte B) ein:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>A<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"> -<\/td><td class=\"has-text-align-left\" data-align=\"left\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">- <\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Versuche gerne einmal selbst (als \u00dcbung) die Matrix \u00fcber alle f\u00fcnf Iterationen zu aktualisieren.<\/p>\n\n\n\n<p>Am Ende sollte sie wie folgt aussehen (alle \u00c4nderungen sind fett markiert):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-regular black-borders-sq\"><table><tbody><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>von \/ nach<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>A<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"> -<\/td><td class=\"has-text-align-left\" data-align=\"left\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">- <\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>B<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>C<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-left\" data-align=\"left\">B<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>D<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>E<\/strong><\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">C<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">E<\/td><\/tr><tr><td class=\"has-text-align-left\" data-align=\"left\"><strong>E<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">A<\/td><td class=\"has-text-align-left\" data-align=\"left\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>A<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><td class=\"has-text-align-center\" data-align=\"center\">-<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Wie k\u00f6nnen wir daraus k\u00fcrzeste Wege ablesen?<\/p>\n\n\n\n<p>Nehmen wir den Weg von D nach B, den wir in der f\u00fcnften Iteration berechnet hatten.<\/p>\n\n\n\n<p>Wir lesen Schritt f\u00fcr Schritt aus der Matrix ab:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Zeile D, Spalte B: Der direkte Nachfolger von D auf dem Weg zu B ist: E<\/li>\n\n\n\n<li>Zeile E, Spalte B: Der direkte Nachfolger von E auf dem Weg zu B ist: A<\/li>\n\n\n\n<li>Zeile A, Spalte B: Der direkte Nachfolger von A auf dem Weg zu B ist: B (Zielknoten erreicht)<\/li>\n<\/ul>\n\n\n\n<p>Der vollst\u00e4ndige k\u00fcrzeste Weg lautet also D\u2192E\u2192A\u2192B.<\/p>\n\n\n\n<p>Hier noch einmal zum Vergleich die Grafik aus der f\u00fcnften Iteration:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"800\" height=\"506\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b.png\" alt=\"Floyd-Warshall-Algorithmus: K\u00fcrzester Weg von D nach B: D\u2192E\u2192A\u2192B\" class=\"wp-image-20509\" style=\"width:400px;height:253px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-224x142.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-336x213.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-504x319.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-672x425.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-400x253.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-example-step5b-600x380.png 600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">K\u00fcrzester Weg von D nach B: D\u2192E\u2192A\u2192B<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Der aus der Nachfolgermatrix abgelesene Pfad stimmt mit dem eingezeichneten Pfad \u00fcberein. <\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"floyd-warshall-algorithmus-informelle-beschreibung\">Floyd-Warshall-Algorithmus \u2013 Informelle Beschreibung<\/h2>\n\n\n\n<p>Die informelle Beschreibung \u2013 und auch der Code (dieser folgt im n\u00e4chsten Kapitel) \u2013 sind \u00fcberraschend einfach. Die Schritte f\u00fcr das Bestimmen der vollst\u00e4ndigen Wege sind als <em>optional<\/em> gekennzeichnet. Um die zwei Matrizen nicht zu verwechseln, bezeichne ich sie im Folgenden als <em>Kostenmatrix<\/em> und <em>Nachfolgermatrix<\/em>.<\/p>\n\n\n\n<p>Vorbereitung:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Erstelle die Kostenmatrix der Gr\u00f6\u00dfe <em>n<\/em> \u00d7 <em>n<\/em> (<em>n<\/em> ist die Anzahl der Knoten).<\/li>\n\n\n\n<li>Trage f\u00fcr jedes Knotenpaar (<em>i<\/em>, <em>j<\/em>) die Kosten des direkten Pfades von <em>i<\/em> nach <em>j<\/em> ein, falls dieser existiert; trage ansonsten <em>unendlich<\/em> ein.   <\/li>\n\n\n\n<li>Trage auf der Diagonalen Nullen ein.<\/li>\n<\/ol>\n\n\n\n<p>Optionale Vorbereitung: Erstellung der Nachfolgermatrix<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Erstelle die Nachfolgermatrix der Gr\u00f6\u00dfe <em>n<\/em> \u00d7 <em>n<\/em>.<\/li>\n\n\n\n<li>Trage f\u00fcr jedes Knotenpaar (<em>i<\/em>, <em>j<\/em>) den Wert <em>j<\/em> ein.<\/li>\n<\/ol>\n\n\n\n<p>F\u00fchre folgende Iteration <em>n<\/em> mal aus; <em>k<\/em> sei dabei der Schleifenz\u00e4hler und stehe f\u00fcr den Zwischenknoten:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F\u00fcr jedes Knotenpaar (<em>i<\/em>, <em>j<\/em>):\n<ul class=\"wp-block-list\">\n<li>Berechne die Summe der Kosten des Weges <em>i<\/em>\u2192<em>k<\/em> (abzulesen in Zeile <em>i<\/em>, Spalte <em>k<\/em> der Kostenmatrix) und der Kosten des Weges <em>k<\/em>\u2192<em>j<\/em> (abzulesen in Zeile <em>k<\/em>, Spalte <em>j<\/em> der Kostenmatrix). <\/li>\n\n\n\n<li>Ist die Summe kleiner als die Kosten des Weges <em>i<\/em>\u2192<em>j<\/em> (abzulesen in Zeile <em>i<\/em>, Spalte <em>j<\/em> der Kostenmatrix), dann\n<ol class=\"wp-block-list\">\n<li>trage die neuen, niedrigeren Kosten in Zeile <em>i<\/em>, Spalte <em>j<\/em> der Kostenmatrix ein;<\/li>\n\n\n\n<li>(optional) kopiere in der Nachfolgermatrix den Wert aus Feld (<em>i<\/em>, <em>k<\/em>) ins Feld (<em>i<\/em>, <em>j<\/em>).<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>Pr\u00fcfe abschlie\u00dfend, ob auf der Diagonalen der Kostenmatrix eine negative Zahl vorkommt. Wenn ja, beende den Algorithmus mit der Fehlermeldung \"Negativer Zyklus erkannt\". Ansonsten ist der Algorithmus erfolgreich durchgelaufen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"floyd-warshall-algorithmus-in-java\">Floyd-Warshall-Algorithmus in Java<\/h2>\n\n\n\n<p>In diesem Kapitel zeige ich dir Schritt f\u00fcr Schritt, wie du den Floyd-Warshall-Algorithmus in Java implementierst. Du findest den vollst\u00e4ndigen Quellcode im <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/tree\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\" target=\"_blank\" rel=\"noopener\">Paket eu.happycoders.pathfinding.floyd_warshall des GitHub-Repositories<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"datenstruktur-fur-den-graph-guava-valuegraph\">Datenstruktur f\u00fcr den Graph: Guava ValueGraph<\/h3>\n\n\n\n<p>Wie auch in den vorangegangenen Teilen der Serie verwenden wir den <a rel=\"noopener\" href=\"https:\/\/guava.dev\/releases\/30.0-jre\/api\/docs\/com\/google\/common\/graph\/MutableValueGraph.html\" target=\"_blank\"><code>MutableValueGraph<\/code><\/a> aus den Google Core Libraries for Java (Guava). Im folgenden Code-Ausschnitt siehst du, wie man den gerichteten Graphen aus dem Beispiel oben erstellt (Methode <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\/TestWithSampleGraph.java#L30\" target=\"_blank\" rel=\"noreferrer noopener\"><code>TestWithSampleGraph.createSampleGraph()<\/code><\/a>): <\/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\">2<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"B\"<\/span>, <span class=\"hljs-string\">\"C\"<\/span>, <span class=\"hljs-number\">6<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"C\"<\/span>, <span class=\"hljs-string\">\"B\"<\/span>, <span class=\"hljs-number\">7<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"D\"<\/span>, <span class=\"hljs-string\">\"C\"<\/span>, <span class=\"hljs-number\">1<\/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\">\"A\"<\/span>, <span class=\"hljs-number\">1<\/span>);\n  graph.putEdgeValue(<span class=\"hljs-string\">\"E\"<\/span>, <span class=\"hljs-string\">\"B\"<\/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 von <code>VaueGraph<\/code> sind:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Typ der Knoten: wir verwenden hier <code>String<\/code> f\u00fcr die Knotennamen \"A\" bis \"E\".<\/li>\n\n\n\n<li>Typ der Kantengewichte: f\u00fcr das Beispiel verwenden wir <code>Integer<\/code>.<\/li>\n<\/ol>\n\n\n\n<p>In der <code>putEdgeValue()<\/code>-Methode wird zuerst der Startknoten angegeben, gefolgt vom Zielknoten und dem Kantengewicht.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"datenstruktur-fur-die-kosten-und-nachfolgermatrix\">Datenstruktur f\u00fcr die Kosten- und Nachfolgermatrix<\/h3>\n\n\n\n<p>Als Datenstruktur f\u00fcr die Matrizen bieten sich zweidimensionale Arrays an:<\/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-keyword\">int<\/span> n = graph.nodes().size();\n<span class=\"hljs-keyword\">int<\/span>&#091;]&#091;] costs = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;n]&#091;n];\n<span class=\"hljs-keyword\">int<\/span>&#091;]&#091;] successors = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;n]&#091;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>Da unser Algorithmus am Ende beide Matrizen zur\u00fcckgeben soll, kapseln wir beide in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\/FloydWarshallMatrices.java\" target=\"_blank\" rel=\"noopener\"><code>FloydWarshallMatrices<\/code><\/a>. Im Repository siehst du, dass diese Klasse auch eine <code>print()<\/code>-Methode hat, mit der wir zum Test die Matrizen auf der Konsole ausgeben k\u00f6nnen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"indizierung-der-knoten-im-graphen\">Indizierung der Knoten im Graphen<\/h3>\n\n\n\n<p>Die Zeilen und Spalten der zweidimensionalen Arrays werden mit Index <em>0<\/em> bis <em>n-1<\/em> adressiert. Unsere Knoten werden allerdings durch Namen identifiziert, nicht durch Zahlen. Wir ben\u00f6tigen also eine Abbildungsvorschrift zwischen Index und Knotenname.<\/p>\n\n\n\n<p>Die Methode <code>graph.nodes()<\/code> liefert ein <code>Set<\/code> der Knoten, also eine nicht indizierbare Datenstruktur.<\/p>\n\n\n\n<p>Wir k\u00f6nnen das Set jedoch sehr einfach in ein Array konvertieren:<\/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\">String&#091;] nodes = graph.nodes().toArray(<span class=\"hljs-keyword\">new<\/span> String&#091;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<p>Mittels <code>nodes[i]<\/code> k\u00f6nnen wir nun f\u00fcr die Zeile oder Spalte <em>i<\/em> den zugeh\u00f6rigen Knotennamen bestimmen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"vorbereitung-fullen-der-matrizen\">Vorbereitung: F\u00fcllen der Matrizen<\/h3>\n\n\n\n<p>Die Matrizen f\u00fcllen wir initial wie folgt (Methode <a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\/FloydWarshall.java#L23\" target=\"_blank\" rel=\"noopener\"><code>FloydWarshall.findShortestPaths()<\/code><\/a>). Die Variable <em>m<\/em> steht hier f\u00fcr die Instanz des <code>FloydWarshallMatrices<\/code>-Klasse, die die zwei Matrizen enth\u00e4lt.<\/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-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> j = <span class=\"hljs-number\">0<\/span>; j &lt; n; j++) {\n    Optional&lt;Integer&gt; edgeValue = graph.edgeValue(nodes&#091;i], nodes&#091;j]);\n    m.costs&#091;i]&#091;j] = i == j ? <span class=\"hljs-number\">0<\/span> : edgeValue.orElse(Integer.MAX_VALUE);\n    m.successors&#091;i]&#091;j] = edgeValue.isPresent() ? j : -<span class=\"hljs-number\">1<\/span>;\n  }\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>In der Kostenmatrix verwenden wir <code>Integer.MAX_VALUE<\/code> als Repr\u00e4sentation f\u00fcr <em>unendlich<\/em>. Das funktioniert nat\u00fcrlich nur, solange wir mit den Kosten nicht in die N\u00e4he dieses Wertes (2<sup>31<\/sup>-1) kommen. F\u00fcr die Demonstration des Algorithmus ist es eine ausreichende Abstraktion.<\/p>\n\n\n\n<p>In der Nachfolgermatrix tragen wir <em>-1<\/em> ein, wenn es f\u00fcr ein Knotenpaar keinen Pfad gibt. <\/p>\n\n\n\n<p>Wir k\u00f6nnten bei beiden Matrizen auch mit <code>Integer<\/code>-Objekten und <code>null<\/code>-Werten arbeiten oder gar mit <code>Optional&lt;Integer&gt;<\/code>, das w\u00e4re allerdings weniger performant.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"iterationen\">Iterationen<\/h3>\n\n\n\n<p>F\u00fcr die Iterationen verschalteln wir drei Schleifen ineinander: <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die \u00e4u\u00dfere, mit Schleifenz\u00e4hler <em>k<\/em>, iteriert \u00fcber die Zwischenknoten.<\/li>\n\n\n\n<li>Die zwei inneren, mit Schleifenz\u00e4hlern <em>i<\/em> und <em>j<\/em>, iterieren \u00fcber alle Knotenpaare.<\/li>\n<\/ul>\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-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> k = <span class=\"hljs-number\">0<\/span>; k &lt; n; k++) {\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-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> j = <span class=\"hljs-number\">0<\/span>; j &lt; n; j++) {\n      <span class=\"hljs-keyword\">int<\/span> costViaNodeK = addCosts(m.costs&#091;i]&#091;k], m.costs&#091;k]&#091;j]);\n      <span class=\"hljs-keyword\">if<\/span> (costViaNodeK &lt; m.costs&#091;i]&#091;j]) {\n        m.costs&#091;i]&#091;j] = costViaNodeK;\n        m.successors&#091;i]&#091;j] = m.successors&#091;i]&#091;k];\n      }\n    }\n  }\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>Innerhalb der Schleifen addieren wir die Kosten der Wege <em>i<\/em>\u2192<em>k<\/em> und <em>k<\/em>\u2192<em>j<\/em> und vergleichen die Summe mit den Kosten des Weges <em>i<\/em>\u2192<em>j<\/em>. Ist die Summe \u00fcber Zwischenknoten <em>k<\/em> kleiner, dann setzen wir die Kosten f\u00fcr den Weg <em>i<\/em>\u2192<em>j<\/em> auf die neu berechneten, geringeren Kosten, und wir setzen als Nachfolgerknoten f\u00fcr den Weg <em>i<\/em>\u2192<em>j<\/em> den Nachfolgerknoten des Weges <em>i<\/em>\u2192<em>k<\/em>.<\/p>\n\n\n\n<p>Die Methode <code>addCosts()<\/code> liefert <em>unendlich<\/em> (in Form von <code>Integer.MAX_VALUE<\/code>) zur\u00fcck, wenn einer der beiden Summanden <em>unendlich<\/em> ist:<\/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-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">addCosts<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> a, <span class=\"hljs-keyword\">int<\/span> b)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (a == Integer.MAX_VALUE || b == Integer.MAX_VALUE) {\n    <span class=\"hljs-keyword\">return<\/span> Integer.MAX_VALUE;\n  }\n  <span class=\"hljs-keyword\">return<\/span> a + b;\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\" id=\"erkennung-von-negativen-zyklen\">Erkennung von negativen Zyklen<\/h3>\n\n\n\n<p>Nach Durchlauf der Iterationen pr\u00fcfen wir auf negative Zyklen:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><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-keyword\">if<\/span> (m.costs&#091;i]&#091;i] &lt; <span class=\"hljs-number\">0<\/span>) {\n    <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"Graph has a negative cycle\"<\/span>);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><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>Am Ende liefert die <code>findShortestPaths()<\/code>-Methode die <code>FloydWarshallMatrices<\/code>-Instanz <em>m<\/em> zur\u00fcck.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"bestimmung-des-kurzesten-pfades-zwischen-zwei-knoten\">Bestimmung des k\u00fcrzesten Pfades zwischen zwei Knoten<\/h3>\n\n\n\n<p>Die Berechnung des k\u00fcrzesten Pfades von einem Knoten zu einem anderen habe ich in der Methode <code><a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\/FloydWarshallMatrices.java#L59\" target=\"_blank\" rel=\"noopener\">FloydWarshallMatrices.getPath()<\/a><\/code> implementiert. <em>i<\/em> und <em>j<\/em> sind dabei die Indizes von Start- und Endknoten:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">if<\/span> (successors&#091;i]&#091;j] == -<span class=\"hljs-number\">1<\/span>) {\n  <span class=\"hljs-keyword\">return<\/span> Optional.empty();\n}\n\nList&lt;String&gt; path = <span class=\"hljs-keyword\">new<\/span> ArrayList&lt;&gt;();\npath.add(nodes&#091;i]);\n\n<span class=\"hljs-keyword\">while<\/span> (i != j) {\n  i = successors&#091;i]&#091;j];\n  path.add(nodes&#091;i]);\n}\n\n<span class=\"hljs-keyword\">return<\/span> Optional.of(List.copyOf(path));<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><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>Zuerst wird gepr\u00fcft, ob <code>successors[i][j]<\/code> gleich <em>-1<\/em> ist. Wenn das der Fall ist, existiert kein Pfad von <em>i<\/em> nach <em>j<\/em>, und die Methode gibt ein leeres <code>Optional<\/code> zur\u00fcck.<\/p>\n\n\n\n<p>Ansonsten wird eine Liste <code>path<\/code> angelegt und mit dem Ausgangsknoten und dann \u2013 nach und nach \u2013 mit den Folgeknoten des Weges bef\u00fcllt. Schlie\u00dflich wird eine nicht modifizierbare Kopie der Liste (Stichwort \"defensive copy\") zur\u00fcckgeliefert.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"aufruf-der-findshortestpaths-methode\">Aufruf der findShortestPaths()-Methode<\/h3>\n\n\n\n<p>Folgende drei Beispiele im Repository zeigen den Aufruf der <code>findShortestPaths()<\/code>-Methode:<\/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\/floyd_warshall\/TestWithSampleGraph.java\" target=\"_blank\" rel=\"noopener\">TestWithSampleGraph<\/a>: In diesem Test werden die k\u00fcrzesten Pfade des Beispielgraphen aus diesem Artikel berechnet.<\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\/TestWithSampleGraphFromBellmanFord.java\" target=\"_blank\" rel=\"noopener\">TestWithSampleGraphFromBellmanFord<\/a>: Dieser Test berechnet die k\u00fcrzesten Pfade in dem <a href=\"\/de\/algorithmen\/bellman-ford-algorithmus-java\/#Beispiel_fur_negative_Kantengewichte\">Beispiel-Graphen<\/a> aus dem Artikel \u00fcber den Bellman-Ford-Algorithmus.<\/li>\n\n\n\n<li><a href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\/TestWithNegativeCycle.java\" target=\"_blank\" rel=\"noopener\">TestWithNegativeCycle<\/a>: Dieser Test ruft die <code>findShortestPaths()<\/code>-Methode f\u00fcr einen <a href=\"\/de\/algorithmen\/bellman-ford-algorithmus-java\/#Was_ist_ein_negativer_Zyklus\">Beispiel-Graphen mit negativem Zyklus<\/a> (ebenfalls aus dem Bellman-Ford-Artikel) auf.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-des-floyd-warshall-algorithmus\">Zeitkomplexit\u00e4t des Floyd-Warshall-Algorithmus<\/h2>\n\n\n\n<p>Die <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">Zeitkomplexit\u00e4t<\/a> des Floyd-Warshall-Algorithmus ist schnell bestimmt. Wir haben drei ineinander geschachtelte Schleifen, die jeweils <em>n<\/em> Durchl\u00e4ufe z\u00e4hlen. In der innersten Schleife haben wir einen Vergleich, der mit konstantem Aufwand durchf\u00fchrbar ist. Der Vergleich wird also <em>n<\/em> \u00d7 <em>n<\/em> \u00d7 <em>n<\/em> mal \u2013 oder n\u00b3 mal \u2013 ausgef\u00fchrt.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t von Floyd-Warshall betr\u00e4gt somit: <em>O(n\u00b3)<\/em><\/p>\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<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-des-floyd-warshall-algorithmus\">Laufzeit des Floyd-Warshall-Algorithmus<\/h2>\n\n\n\n<p>Mit dem Programm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/pathfinding\/blob\/main\/src\/main\/java\/eu\/happycoders\/pathfinding\/floyd_warshall\/TestFloydWarshallRuntime.java\" target=\"_blank\">TestFloydWarshallRuntime<\/a> k\u00f6nnen wir pr\u00fcfen, ob die Laufzeit des Algorithmus zur hergeleiteten Zeitkomplexit\u00e4t <em>O(n\u00b3)<\/em> passt. Das Programm erstellt zuf\u00e4llige Graphen verschiedener Gr\u00f6\u00dfen und berechnet darin die k\u00fcrzesten Pfade. Das Programm wiederholt jeden Test 50 mal und gibt den Median aller Messwerte aus.<\/p>\n\n\n\n<p>Das folgende Diagramm zeigt die Laufzeit in Abh\u00e4ngigkeit von der Gr\u00f6\u00dfe des Graphen:<\/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\/04\/floyd-warshall-time-complexity.png\" alt=\"Zeitkomplexit\u00e4t des Floyd-Warshall-Algorithmus\n\" class=\"wp-image-20563\" style=\"width:800px;height:500px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-time-complexity-944x590.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t des Floyd-Warshall-Algorithmus<br><\/figcaption><\/figure>\n<\/div>\n\n\n<p>Das kubische Wachstum ist gut zu erkennen: Bei Verdopplung der Anzahl der Knoten (z. B. von 1.000 auf 2.000) verachtfacht sich die ben\u00f6tigte Zeit (von 700 ms auf etwa 6 s).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"floyd-warshall-vs-bellman-ford-vs-dijkstra\">Floyd-Warshall vs. Bellman-Ford vs. Dijkstra<\/h3>\n\n\n\n<p>Im folgenden Diagramm habe ich die Laufzeiten von Floyd-Warshall, Bellman-Ford (optimiert und nicht optimiert) und Dijkstra (mit Fibonacci Heap) gegen\u00fcbergestellt:<\/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\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra.png\" alt=\"Zeitkomplexit\u00e4t Floyd-Warshall-Algorithmus vs. Bellman-Ford vs. Dijkstra\" class=\"wp-image-20564\" style=\"width:800px;height:500px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-224x140.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-336x210.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-504x315.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-672x420.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-400x250.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-600x375.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-800x500.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-vs-bellman-ford-vs-dijkstra-944x590.png 944w\" sizes=\"(max-width: 1200px) 100vw, 1200px\" \/><figcaption class=\"wp-element-caption\">Zeitkomplexit\u00e4t Floyd-Warshall-Algorithmus vs. Bellman-Ford vs. Dijkstra<br><\/figcaption><\/figure>\n<\/div>\n\n\n<p>Floyd-Warshall ist, wie aufgrund der Zeitkomplexit\u00e4t zu erwarten war, noch einmal langsamer als Bellman-Ford.<\/p>\n\n\n\n<p>Wann sollte also welcher Algorithmus eingesetzt werden?<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Floyd-Warshall sollte nur dann eingesetzt werden, wenn die k\u00fcrzesten Wege zwischen <em>allen<\/em> Knotenpaaren gesucht werden.<\/li>\n\n\n\n<li><a href=\"\/de\/algorithmen\/bellman-ford-algorithmus-java\/\">Bellman-Ford<\/a> sollte eingesetzt werden, wenn der Graph negative Kantengewichte enth\u00e4lt.<\/li>\n\n\n\n<li><a href=\"\/de\/algorithmen\/a-stern-algorithmus-java\/\">A*<\/a> sollte eingesetzt werden, wenn der Graph keine negativen Kantengewichte enth\u00e4lt und sich eine Heuristik definieren l\u00e4sst.<\/li>\n\n\n\n<li>Ohne negative Kantengewichte und ohne Heuristik sollte <a href=\"\/de\/algorithmen\/dijkstra-algorithmus-java\/\">Dijkstras Algorithmus<\/a> eingesetzt werden.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusammenfassung\">Zusammenfassung<\/h2>\n\n\n\n<p>Dieser Artikel hat dir gezeigt, wann man den Floyd-Warshall-Algorithmus einsetzt (wenn man die k\u00fcrzesten Entfernungen zwischen <em>allen<\/em> Knotenpaaren ben\u00f6tigt), wie er funktioniert und wie er negative Zyklen identifiziert.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t ist mit <em>O(n\u00b3)<\/em> deutlich schlechter als die aller bisher vorgestellten Pathfinding-Algorithmen. Floyd-Warshall sollte daher wirklich nur f\u00fcr den vorgesehenen Einsatzzweck verwendet werden.<\/p>\n\n\n\n<p>Damit endet die Serie \u00fcber Pathfinding-Algorithmen. Hast du Fragen oder Anregungen? Dann hinterlasse mir gerne einen Kommentar.<\/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 Floyd-Warshall-Algorithmus und wann setzt man ihn ein? Welche Varianten gibt es? Wie bestimmt man die Zeitkomplexit\u00e4t von Floyd-Warshall?<\/p>\n","protected":false},"author":1,"featured_media":43222,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Floyd-Warshall-Algorithmus \u2013 Schritt f\u00fcr Schritt erkl\u00e4rt \u2013 einfach + mit einem Java-Beispiel. Au\u00dferdem: Wie bestimmt man die Zeitkomplexit\u00e4t?","_seopress_robots_index":"","_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":28251,"_post_count":0,"footnotes":""},"categories":[127],"tags":[137],"class_list":["post-20425","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\/04\/floyd-warshall-algorithm-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-algorithm-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/04\/floyd-warshall-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":2,"uagb_excerpt":"Wie funktioniert der Floyd-Warshall-Algorithmus und wann setzt man ihn ein? Welche Varianten gibt es? Wie bestimmt man die Zeitkomplexit\u00e4t von Floyd-Warshall?","public_identification_id":"6cebb74374bc4ffe894ed8bec9f1c668","private_identification_id":"99f0411dd1744d2486260a033cad7cea","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20425","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=20425"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20425\/revisions"}],"predecessor-version":[{"id":52494,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/20425\/revisions\/52494"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43222"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=20425"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=20425"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=20425"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}