AuK/Kürzeste Wege WS13-14

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==
[[Bild:S3ankrau_Ungerichteter-gewichteter-graph.gif|right|thumb|250px|Graphendarstellung]]

Das kürzeste Wege Problem beschränkt sich auf die Betrachtung von Graphen, die Gegenstand der Graphentheorie sind. 

Ein endlicher Graph $G$ besteht im Wesentlichen aus zwei endlichen Mengen, nämlich der Knotenmenge $V$ (engl.:''Vertices'') und der Kantenmenge $E$ (engl.:''Edges''). 

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

 <math> c \colon E \to \mathbb{R}_+ </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>

==Dijkstra-Algorithmus==

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==
==Bellman-Ford-Algorithmus==

Der Bellman-Ford-Algorithmus kann mit negativen Kosten arbeiten. Diese können beispielsweise für einen Taxifahrer entstehen, wenn er einen Fahrgast transportiert und für die Fahrt mehr Geld einnimmt, als ihn Benzin und Fahrzeug für die Fahrt kosten. Fährt er ohne Fahrgast, sind seine Kosten positiv.

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

<br><br>

=Übung=