AuK/Kürzeste Wege WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
'''Autoren''': [mailto:s3ankrau@stud.hszg.de Andre Krause], [mailto:s3rostan@stud.hszg.de Roman Stange]
=Kürzeste Wege=
==Motivation==
[[Bild:S3ankrau_Sachsen-strassennetz.JPG|right|thumb|250px|Straßennetz Sachsen]]
Im Alltag spielt das kürzeste Wege Problem eine große Rolle. Wollen wir zum Beispiel mit dem Auto einen Ort ansteuern, dessen Anfahrt uns unbekannt ist, wird häufig ein Navigationssystem genutzt. Dabei gibt es immer die Möglichkeit, zwischen der schnellsten oder der kürzesten Route zu entscheiden. Beide Varianten haben ihre Vor- und Nachteile: Bei der schnellsten Route braucht man vermeintlich weniger Zeit um zum Ziel zu gelangen, es könnte aber die wesentlich längere Strecke sein. Die kürzeste Route hingegen könnte die geringste Kilometerzahl bedeuten, jedoch auch eine deutlich höhere Fahrzeit. Dabei sind die Werte für Zeit und Entfernung immer die Gewichtung der Kanten zwischen den Knoten. Ein ähnliches Beispiel lässt sich auch für das Streckennetz der Eisenbahn aufstellen. Das Problem der kürzesten Wege besteht im Prinzip darin, dass im Gegensatz zum [[AuK/Verzweigen_und_beschränken_WS13-14#Das_Rundreiseproblem|Rundreiseproblem]] auch alle Zwischenstädtefolgen (Wege) betrachtet werden müssen. Also auch die, die nicht alle Städe enthalten. Da bei einer großen Anzahl n von betrachteten Städten die Wegfindung nicht mehr so leicht überschaubar ist, benötigt es Algorithmen, die dieses Problem adäquat lösen können.
===Exkurs===
Was haben Hummeln mit dieser Thematik zu tun? Die Insekten sind offensichtlich in der Lage, das sogenannte Problem des Handlungsreisenden (TSP) zu lösen. Die Herausforderung besteht darin, auf dem kürzesten Weg jede Blume anzusteuern und dann zum Hummelnest zurückzufliegen. Forscher folgern, dass es den Brummern gelingt, durch Anwendung von ''Trial und Error'' die annähernd kürzeste Route zu ermitteln. Wenn die neue Wegstrecke kürzer ist, dann geben sie die alte auf und wechseln zur nächstbesten Lösung. So fanden die Hummeln die kürzeste Route, nachdem sie 20 von 120 möglichen Wegen ausprobiert hatten. [http://www.welt.de/wissenschaft/article109385090/Hummeln-loesen-Navi-Aufgaben-verblueffend-effektiv.html]
<br><br>
==Graphentheorie==
Das kürzeste Wege Problem beschränkt sich auf die Betrachtung von Graphen, die Gegenstand der Graphentheorie sind. In der Graphentheorie werden unterschiedliche Graphentypen und deren Eigenschaften analysiert. Allgemein besteht ein endlicher Graph $G$ im Wesentlichen aus zwei endlichen Mengen, nämlich der Knotenmenge $V$ (engl.:''Vertices'') und der Kantenmenge $E$ (engl.:''Edges''). Zeichnerisch lassen sich die Knoten eines Graphen durch Punkte und Kanten durch Verbindungslinien darstellen.
<math> G = (V,E) </math>
Eine Kante verbindet dabei zwei Konten. Ein Knoten kann mit mehreren anderen verbunden sein. Es ist aber nicht zwingend notwendig, dass alle Knoten miteinander verbunden sind. <br>
Um eine Orientierung für den kürzesten Weg auszumachen, werden den Kanten Gewichte zugeordnet, die mit folgender Kostenfunktion ausgedrückt werden kann:
<math> w \colon E \to \mathbb{R} </math>
<br>
[[Bild:Visvitalis_Gewicht.png|right|thumb|400px|<math>w(p)=2</math>]]
Das Gewicht eines Pfades <math>p = (v_0,v_1, \ldots ,v_k) </math> ist definiert als <math> w(p):= \sum_{i=0}^{k-1} w|(v_i, v_{i+1} ) </math><br>
Die Gewichtung einer Kante oder eines Pfades (= Distanz zwischen einem Startknoten $s$ zu einen beliebigen anderen Zielknoten $t$ mit der Eigenschaft, Element der Knotenmenge $V$ von $G$ zu sein) entspricht nicht immer zwangsläufig einer Längenangabe. Man kann auch die Fahrzeit eines Weges betrachten oder, ob man für dessen Benutzung Geld zahlen muss – oder Geld erhält. <br>
Weitere Eigenschaften:
* '''gerichtet/ungerichtet''': Richtung der Kanten angegeben/nicht angegeben
* '''gewichtet/ungewichtet''': Gewichtung (z.B. Entfernung) der Kanten angegeben/nicht angegeben
* '''einfach/multigraph''': keine Mehrfachkanten/mit Mehrfachkanten
<br><br>
==kürzeste Wege==
Man nennt einen Pfad <math>p</math> einen kürzesten Pfad von(Startknoten) <math>s</math> nach (Endknoten) <math>t</math>, falls <math>w(p) = \delta(u,v)</math>.
<math>s,t \in V:
\delta(u,v) = \begin{cases}
min \lbrace w(p)| p = s \leadsto t \rbrace & \text{,falls ein solcher Pfad existiert}\\
\infty & \text{,sonst}
\end{cases}</math>
<br>
Kürzeste Pfade ''müssen'' nicht existieren:<br>
1. Fall: Ein kürzester Pfad von $s$ nach $t$ existiert nicht, wenn gar kein Pfad von $s$ nach $t$ existiert.<br>
2. Fall: Ein kürzester Pfad existiert nicht, wenn es einen Zyklus mit einem negativen Gesamtgewicht gibt.<br>
[[Bild:Visvitalis_Negatives_Gesamtgewicht.png|400px]]
<br><br>
==Dijkstra-Algorithmus==
Ein Algorithmus zur Lösung des Kürzesten-Wege Problems fand 1959 der niederländische Informatiker Edsger W. Dijkstra, nach dem auch der Algorithmus benannt wurde. Dieser gehört zur Klasse der Greedy-Algorithmen und seine Rechenzeit befindet sich bei $\mathcal{O}(n^2)$. Zur Findung des kürzesten Weges wird sukzessiv der nächst beste Knoten in eine Ergebnismenge aufgenommen und aus den zu bearbeitenden entfernt, solange bis der Zielknoten erreicht wird.
'''Funktionsweise:'''<br>
1:Gehe vom Startpunkt aus jeden angrenzenden Weg mit der gleichen Geschwindigkeit entlang, bis man auf einen weiteren Knotenpunkt trifft.<br>
2:Von jedem erreichten Knotenpunkt gehe alle weiteren angrenzenden Wege entlang.<br>
3:Wird dabei eine Stelle ein zweites Mal passiert, wird der Weg als ungültig markiert.<br>
4:Wiederhole, bis Zielpunkt auftrifft.<br>
Als Beispiel für den Dijkstra-Algorithmus wird folgender Graph benutzt. Gesucht ist die kürzeste Strecke von A nach I.
<center>
<table border="1">
<tr>
<td>[[Bild:S3ankrau_Step1.jpg|400px]]<br><center>'''Schritt 1'''</center></td>
<td>[[Bild:S3ankrau_Step2.jpg|400px]]<br><center>'''Schritt 2'''</center></td>
<td>[[Bild:S3ankrau_Step3.jpg|400px]]<br><center>'''Schritt 3'''</center></td>
</tr>
<tr>
<td>[[Bild:S3ankrau_Step4.jpg|400px]]<br><center>'''Schritt 4'''</center></td>
<td>[[Bild:S3ankrau_Step5.jpg|400px]]<br><center>'''Schritt 5'''</center></td>
<td>[[Bild:S3ankrau_Step6.jpg|400px]]<br><center>'''Schritt 6'''</center></td>
</tr>
<tr>
<td>[[Bild:S3ankrau_Step7.jpg|400px]]<br><center>'''Schritt 7'''</center></td>
</tr>
</table>
</center>
Der kürzeste Weg von A nach I besteht also aus den Kantenfolgen $(A, B)$, $(B, G)$, $(G,I)$ mit der Länge 8.
==Floyd-Warshall-Algorithmus==
Der Floyd-Warshall Algorithmus geht zurück auf die Informatiker Robert Floyd und Stephen Warshall. Im Prinzip handelt es sich dabei um zwei Algorithmen:
* Zum einen findet er die Länge der kürzesten Wege zwischen allen Paaren von Knoten eines gewichteten Graphen nach Floyd
* Zum anderen die [http://de.wikipedia.org/wiki/Transitive_H%C3%BClle_%28Relation%29 transitive] Hülle eines Graphen nach Warshall
===Floyd-Algorithmus===
Es ist ein Graph gegeben durch seine Gewichtsmatrix $w$. $w[i,j]$ ist dabei das Gewicht der Kante von $i$ nach $j$, falls eine Kante existiert (sollte es keine Kante geben, so ist das Gewicht unendlich).
Die Distanzmatrix $d$, welche die kürzesten Distanzen zwischen allen Knotenpaaren enthält, kann durch folgendes Verfahren bestimmt werden:
*Für alle $i,j$: $d[i,j] = w[i,j]$
**Für $k = 1$ bis $n$
***Für alle Paare $i,j$
****$d[i,j]$ = $min$($d[i,j]$, $d[i,k]$ + $d[k,j]$)
===Warshall-Algorithmus===
Um nun die transitive Hülle zu berechnen, wird zu dem Graphen eine Adjazenzmatrix $w$ aufgestellt. Dabei ist $w[i,j]$ gleich 1, falls eine Kante von $i$ nach $j$ existiert, 0 falls nicht.
Die Matrix $d$ wird nun so berechnet, dass $d[i,j]$ 1 ist, wenn ein Pfad von $i$ nach $j$ existiert.
*Für alle $i,j$: $d[i,j] = w[i,j]$
**Für $k = 1$ bis $n$
***Für alle Paare $i,j$
****Falls $d[i,j] = 0$
*****$d[i,j]$ = $d[i,k]$ * $d[k,j]$
<language>Java</language>
===Floyd-Warshall Algorithmus===
Der Floyd-Algorithmus berechnet an sich nur die Länge des kürzesten Weges. Um aber nun den kürzesten Weg zu konstruieren, wird eine zweite Matrix $F$ erzeugt, in dem jeweils der vorherige Knoten auf dem kürzesten Weg von $i$ nach $j$ in $F[i,j]$ gespeichert wird. Sollte der Floyd-Algorithmus einen kürzeren Weg von $i$ nach $j$ finden, so wird der Eintrag bei $F[i,j]$ aktualisiert.
'''Funktionsweise:'''<br>
1: ermittle Distanzen zwischen nebeneinanderliegenden Knoten<br>
2: prüfe ob Distanz zwischen zwei Knoten durch Hinzunahme eines anderen Knoten kürzer wird<br>
3: wiederhole 2 mit allen anderen Knoten<br>
Als Beispiel soll der kürzeste Weg von 1 nach 4 im folgenden Graphen gefunden werden.
<center>
<table>
<tr>
<td>
<table border="1">
<tr>
<td tyle="text-align: center;">[[Bild:S3ankrau_Floyd_before.jpg|200px]]</td>
</tr>
<tr>
<td>
<table border="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$W[i,j]$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">12</td>
<td style="text-align: center;width: 5mm;">inf</td>
<td style="text-align: center;width: 5mm;">inf</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">inf</td>
<td style="text-align: center;width: 5mm;">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm;">12</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">9</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm;">inf</td>
<td style="text-align: center;width: 5mm;">inf</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
<td style="text-align: center;width: 5mm;">inf</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">0</td>
</tr>
</table>
</td>
<td>
<table border="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$F[i,j]$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">1</td>
<td style="text-align: center;width: 5mm;">1</td>
<td style="text-align: center;width: 5mm;">-</td>
<td style="text-align: center;width: 5mm;">-</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">-</td>
<td style="text-align: center;width: 5mm;">2</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">3</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm;">-</td>
<td style="text-align: center;width: 5mm;">-</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">4</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
<td style="text-align: center;width: 5mm;">-</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">x</td>
</tr>
</table>
</td>
</tr>
</table>
</td>
<td>
[[Bild:S3ankrau_Arrow.png|100px]]
</td>
<td>
<table border="1">
<tr>
<td><center>[[Bild:Floyd_finish.jpg|200px]]</center></td>
</tr>
<tr>
<td>
<table border="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$W[i,j]$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm; color:red;">7</td>
<td style="text-align: center;width: 5mm; color:red;">14</td>
<td style="text-align: center;width: 5mm; color:red;">8</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm; color:red;">11</td>
<td style="text-align: center;width: 5mm;">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm; color:red;">7</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">9</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm; color:red;">14</td>
<td style="text-align: center;width: 5mm; color:red;">11</td>
<td style="text-align: center;width: 5mm;">10</td>
<td style="text-align: center;width: 5mm;">0</td>
<td style="text-align: center;width: 5mm;">6</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
<td style="text-align: center;width: 5mm; color:red;">8</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">9</td>
<td style="text-align: center;width: 5mm;">6</td>
<td style="text-align: center;width: 5mm;">0</td>
</tr>
</table>
</td>
<td>
<table border="1">
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">$F[i,j]$</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">1</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">1</td>
<td style="text-align: center;width: 5mm; color:red;">2</td>
<td style="text-align: center;width: 5mm; color:red;">5</td>
<td style="text-align: center;width: 5mm; color:red;">2</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">2</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">2</td>
<td style="text-align: center;width: 5mm; color:red;">5</td>
<td style="text-align: center;width: 5mm;">2</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">3</td>
<td style="text-align: center;width: 5mm; color:red;">2</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">3</td>
<td style="text-align: center;width: 5mm;">3</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">4</td>
<td style="text-align: center;width: 5mm; color:red;">5</td>
<td style="text-align: center;width: 5mm; color:red;">5</td>
<td style="text-align: center;width: 5mm;">4</td>
<td style="text-align: center;width: 5mm;">x</td>
<td style="text-align: center;width: 5mm;">4</td>
</tr>
<tr>
<td style="text-align: center;width: 5mm;" bgcolor="#D8D8D8">5</td>
<td style="text-align: center;width: 5mm; color:red;">2</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">5</td>
<td style="text-align: center;width: 5mm;">x</td>
</tr>
</table>
</td>
</tr>
</table>
</td>
</tr>
</table>
</center>
<br><br>
==Bellman-Ford-Algorithmus==
Mit dem Bellman-Ford-Algorithmus (benannt nach seinen Erfindern Richard E. Bellman und Lester R. Ford jr.) kann ausgehend von einem Startknoten in einem kantengewichteten Graphen auch mit negativen Kosten den kürzesten Weg finden. Diese negativen Gewichte können beispielsweise für einen Taxiunternehmer entstehen, wenn er einen Fahrgast transportiert und für die Fahrt mehr Geld einnimmt, als ihn Sprit und Unterhalt für die Fahrt kosten. Fährt er ohne Fahrgast, sind seine Kosten positiv. <br><br>
'''Funktionsweise:'''<br>
1: betrachte jede Kante<br>
2: aktualisiere die Distanz und(!) die Vorgänger der zugehörigen Knoten<br>
3: wiederhole |V|-1 mal<br>
<center>
<table border="1">
<tr>
<td>[[Bild:Visvitalis_BellmanFord_s_01.png|400px]]<br><center>'''Schritt 1'''</center></td>
<td>[[Bild:Visvitalis_BellmanFord_s_02.png|400px]]<br><center>'''Schritt 2'''</center></td>
<td>[[Bild:Visvitalis_BellmanFord_s_03.png|400px]]<br><center>'''Schritt 3'''</center></td>
</tr>
<tr>
<td>[[Bild:Visvitalis_BellmanFord_s_04.png|400px]]<br><center>'''Schritt 4'''</center></td>
<td>[[Bild:Visvitalis_BellmanFord_s_05.png|400px]]<br><center>'''Schritt 5'''</center></td>
<td>[[Bild:Visvitalis_BellmanFord_s_06.png|400px]]<br><center>'''Schritt 6'''</center></td>
</tr>
<tr>
<td>[[Bild:Visvitalis_BellmanFord_s_07.png|400px]]<br><center>'''Schritt 7'''</center></td>
<td>[[Bild:Visvitalis_BellmanFord_s_08.png|400px]]<br><center>'''Schritt 8'''</center></td>
<td>[[Bild:Visvitalis_BellmanFord_s_09.png|400px]]<br><center>'''Schritt 9'''</center></td>
</tr>
<tr>
<td>[[Bild:Visvitalis_BellmanFord_s_10.png|400px]]<br><center>'''Schritt 10'''</center></td>
</tr>
</table>
</center>
Ein weiteres wichtiges Merkmal des Bellman-Ford Algorithmus ist, dass er auf Kreise/Schleifen mit negativem Gewicht reagieren sollte. Enthält ein Graph nämlich einen Kreis negativer Länge als Teil eines Weges von $s$ nach $t$, dann könnte der Kreis beliebig oft durchlaufen und die Länge des Weges damit immer noch kürzer gemacht werden und nie zum Ziel führen. Angenommen, alle n-1 Iterationen wurden durchlaufen, so muss noch auf negative Schleifen im Graphen geprüft werden. Hierfür werden noch einmal alle Kanten aus $E$ nach obigem Prinzip durchlaufen und geprüft, ob sich immer noch eine Knotendistanz verbessern lässt. Dies ist nur der Fall, wenn im Graph eine Rückkopplung existiert, die mindestens eine Kante mit negativem Kantengewicht beinhaltet. In diesem Fall bricht der Algorithmus ab und gibt dafür eine Meldung aus.
====Komplexität====
Die Laufzeit des Algorithmus ist in <math>\mathcal{O} \left( n \cdot m \right) </math>, wobei $n$ die Anzahl der Knoten und $m$ die Anzahl der Kanten im Graphen sind. Will man die kürzesten Wege von jedem Knoten zu jedem anderen Knoten finden, so muss man den Algorithmus für jeden Startknoten einmal anwenden, insgesamt also n-mal. Die Laufzeitkomplexität dafür beträgt folglich <math>\mathcal{O} \left( n^2 \cdot m \right)</math> .
==Zeitkomplexität - Vergleich==
{|class="wikitable" style="border: 2px solid lightgray; margin:20px 20px 1em 1em; padding-right: 10px;"
! colspan="4" style="background-color:limegreen; width:20%"|Zeitvergleich verschiedener Graphenalgorithmen
|-
|
|'''Dijkstra'''
|'''Bellman Ford'''
|'''Floyd Warshall'''
|-
|'''Laufzeit'''
|<math>\mathcal{O}(|V|^2)</math>
|<math>\mathcal{O}(|V|\cdot|E|)</math>
|<math>\mathcal{O}(|V|^3)</math>
|}
=Übung=
==Floyd-Warshall-Algorithmus==
<popup name="Übung">
Es ist folgender Graph gegeben:
[[Bild:S3ankrau_Graph_Floyd_Warshall_Übung.jpg|250px]]
Schreiben Sie für diesen Graph ein Programm in der Sprache Ihrer Wahl, mit dem das kürzeste Wege Problem mit dem Floyd-Warshall-Algorithmus gelöst werden kann. Orientieren Sie sich am Pseudo-Code aus dem Abschnitt des genannten Algorithmus. Folgender Java Code dient als Orientierung:
<code id="52c93826ad4dc">
public class FloydWarshall {
private static int n = 5;
private static int INF = 999;
public static void main (String[] args){
int graph[][] = //TODO
floydWarshall(graph);
}
public static void floydWarshall (int graph[][])
{
//TODO
}
public static void printSolution(int dist[][])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (dist[i][j] == INF)
System.out.print("INF ");
else
System.out.print(dist[i][j] + " ");
}
System.out.print("\n");
}
}
}
</code>
</popup>
==Lösung==
===Floyd-Warshall-Algorithmus===
<popup name="Lösung">
<code id="52c93abe5f495">
int graph[][] = { {0, 2, 3, INF, INF},
{INF, 0, INF, 9, INF},
{INF, 7, 0, INF, 5},
{INF, INF, INF, 0, INF},
{INF, INF, INF, 1, 0}
};
public static void floydWarshall (int graph[][])
{
int dist[][] = new int[n][n], i, j, k;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
</code>
Ergebnistabelle:<br>
0 | 2 | 3 | 9 | 8<br>
INF | 0 | INF | 9 | INF<br>
INF | 7 | 0 | 6 | 5<br>
INF | INF | INF | 0 | INF<br>
INF | INF | INF | 1 | 0<br>
</popup>