Kürzeste Wege WS13-14
Inhaltsverzeichnis |
Autoren: Andre Krause, Roman Stange
Kürzeste Wege
Motivation
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 Rundreiseproblem (LINK!!!!) 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.
Graphentheorie
Das kürzeste Wege Problem beschränkt sich auf die Betrachtung von Graphen, die Gegenstand der Graphentheorie sind. Dabei besteht der (endliche) Graph immer aus einem Paar (V, E), wobei V eine endliche Menge von Knoten und E eine endliche Menge von Kanten bezeichnet. 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.
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