Aus ProgrammingWiki

Autoren: Andre Krause, Roman Stange

Kürzeste Wege

Motivation

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 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 und ihren Mitstreitern über Duftstoffverteilung mitzuteilen. 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. [1]

Graphentheorie

Beispiel

	Weg	Pfad	Kreis
(d b a c)	–	–	–
(b c b a c e)	✓	–	–
(e c b a)	✓	✓	–
(c a b)	✓	✓	✓
(d c)	✓	✓	–

Das kürzeste Wege Problem beschränkt sich auf die Betrachtung von Graphen, die Gegenstand der Graphentheorie sind, in welcher unterschiedliche Graphentypen und deren Eigenschaften analysiert werden. 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 Kreise bzw. Punkte und Kanten durch Verbindungslinien darstellen. Eine Kante verbindet dabei zwei Konten. Ein Knoten wiederum kann mit mehreren anderen verbunden sein. Es ist aber nicht zwingend notwendig, dass alle Knoten miteinander verbunden sind. Stellt man sich den Graph dann vielleicht als Repräsentation eines Stadtplan mit Sehenswürdigkeiten vor, erscheint es logisch darin Wege zu interpretieren.

Ein Weg $W$ von einem Anfangsknoten $s$ zu einem Zielknoten $t$ ist dabei eine nichtleere, endliche Menge von Knoten, wenn die jeweils aufeinander folgenden Knoten durch eine Kante verbunden sind. Wiederholungen von Knoten und Kanten ist dabei zugelassen.

 für  und 
Anfangsknoten, Zielknoten, Länge des Weges:

Ein Pfad ist ein Weg in $G$, in dem alle Knoten paarweise verschieden sind. Im Kreis (englisch: cycle) bewegt man sich, wenn Start- und Endknoten eines Pfades gleich sind. Es gilt also zusätzlich: $v_i \neq v_j$ für $s, t \in \{ 1, \ldots , n-1 \}$ mit $s \neq t$ bei einer Länge $\, l \geq 3$ .

Um eine Orientierung für den kürzesten Weg zu bekommen, werden den Kanten Gewichte zugeordnet, die mit folgender Kostenfunktion ausgedrückt werden kann, wonach die Menge der Kanten in die Menge der reellen Zahlen abgebildet wird:

$w(p)=2$

Die Gewichtung einer Kante oder eines Pfades entspricht nicht immer zwangsläufig Längenangaben. Man kann auch die Fahrzeit eines Weges betrachten oder, ob man für dessen Benutzung Geld zahlen muss – oder Geld erhält, oder Steigungen, etc.

Das Gewicht eines Pfades $p = (v_0,v_1, \ldots ,v_l) \,$ ist definiert als:

kürzester Weg

Bezeichnen wir mit $P(u,v)$ die Menge von Knoten $u$ nach Knoten $v$, so ist die Distanz $\delta \,$ zwischen $u$ und $v$

Zyklus innerhalb eines Weges mit negativem Gesamtgewicht

Ein kürzester Weg $p$ von $u$ nach $v$ ist dann ein Weg $p \in P(u,v)$ mit $w(p)=\delta(u,v)$ .

Der Weg $p$ von einem Startknoten $s$ nach einem Endknoten $t$ in einem Graphen $G$ ist nach obiger Definition eben der kürzeste wenn gilt, dass sein Gewicht $w(p)$ unter allen möglichen Wegen minimal ist. Zudem muss noch entschieden werden, ob $t$ von $s$ überhaupt sinnvoll erreichbar ist.

Kürzeste Pfade müssen nicht existieren:
1. Fall: Ein kürzester Pfad von $s$ nach $t$ existiert nicht, wenn gar kein Pfad von $s$ nach $t$ existiert.
2. Fall: Ein kürzester Pfad existiert nicht, wenn es einen Zyklus ( = gerichteter Weg mit gleichem Anfangs- und Endknoten) mit einem negativen Gesamtgewicht gibt.

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:
1.) Gehe vom Startpunkt aus den Weg mit der geringsten Gewichtung entlang (zugehörige Knoten wird aufgenommen).
2.) Prüfe, ob mit neuem Knoten sich kürzere Wege ergeben (falls ja, streiche den längeren Weg).
3.) Wiederhole, bis Zielpunkt erreicht wird.

Als Beispiel für den Dijkstra-Algorithmus wird folgender Graph benutzt. Gesucht ist die kürzeste Strecke von A nach I.

Schritt 1	Schritt 2	Schritt 3
Schritt 4	Schritt 5	Schritt 6

Der kürzeste Weg von A nach I besteht also aus den Kantenfolgen $(A, B)$, $(B, G)$, $(G,I)$ mit der Länge 8.

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 der kürzeste Weg gefunden werden. 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.
Der kürzeste Weg ist gefunden, wenn man sich zwischen zwei Durchgängen nicht mehr verbessert, spätestens aber nach $n-1$ Durchgängen. Nach dem $n-1$ . Durchgang wird noch eine Iteration zur Prüfung durchgeführt. Wenn es in diesem Durchgang eine weitere Verbesserung gibt, ist es einen negativen Zykel und damit keinen eindeutig kürzesten Weg. So oder so stoppt hier der Algorithmus.

Funktionsweise:
1.) Prüfe durchgangsbasiert jede Kante, ob ihre Verwendung die Distanz vom Startknoten zu ihrem Endknoten reduziert.
2.) Aktualisiere die Distanz und(!) die Vorgänger der zugehörigen Knoten.
3.) Wiederhole |V|-1 Mal.
4.) Vermelde einen Teufelskreis, wenn nach |V|-1 immer noch Verbesserungen möglich sind.

Schritt 1	Schritt 2	Schritt 3
Schritt 4	Schritt 5	Schritt 6
Schritt 7	Schritt 8	Schritt 9
Schritt 10

Der kürzeste Weg wurde gefunden mit der Kantenfolge: $(A,C),(C,H),(H,I) \,$ mit der Länge -2.

Komplexität

Die Laufzeit des Algorithmus ist in $\mathcal{O} \left( n \cdot m \right)$ , 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 $\mathcal{O} \left( n^2 \cdot m \right)$ .

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 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]$

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:
1.) Ermittle alle Distanzen zwischen jedem Knotenpaar (falls vorhanden).
2.) Gib nacheinander jeden Knoten frei.
3.) Prüfe, ob sich mit dem neuen Knoten minimale Wege ergeben.
4.) Wiederhole solange, bis alle Knoten freigegeben wurden und es keine Verbesserungen gibt.

Als Beispiel soll der kürzeste Weg von 1 nach 4 im folgenden Graphen gefunden werden.

$W[i,j]$	1	2	3	4	5
1	0	3	12	inf	inf
2	3	0	4	inf	5
3	12	4	0	10	9
4	inf	inf	10	0	6
5	inf	5	9	6	0

$F[i,j]$	1	2	3	4	5
1	x	1	1	-	-
2	2	x	2	-	2
3	3	3	x	3	3
4	-	-	4	x	4
5	-	5	5	5	x

$W[i,j]$	1	2	3	4	5
1	0	3	7	14	8
2	3	0	4	11	5
3	7	4	0	10	9
4	14	11	10	0	6
5	8	5	9	6	0

$F[i,j]$	1	2	3	4	5
1	x	1	2	5	2
2	2	x	2	5	2
3	2	3	x	3	3
4	5	5	4	x	4
5	2	5	5	5	x

Zeitkomplexität aller drei Algorithmen

Das Entscheidungsproblem, ob es einen kürzesten Weg gibt ist NP-vollständig und lässt sich vermutlich nicht effizient lösen. Dementsprechend kann im Allgemeinen auch ein kürzester Pfad vermutlich nicht in Polynomialzeit gefunden werden. Dennoch kann man Fälle spezifizieren und die Bestimmung kürzester Pfade in Polynomialzeit ist trotz der Komplexität des Problems möglich. Die wichtigste Einschränkung betrifft hier die Gewichtsfunktion:

konservative Gewichtsfunktion für alle Zyklen $C$ vom Graph $G$:

Für konservative Gewichtsfunktionen lassen sich kürzeste Wege in Polynomialzeit bestimmen, hierzu kann zum Beispiel der Bellman-Ford-Algorithmus verwendet werden. Wenn man zusätzlich Nichtnegativität verlangt, lässt sich das Problem mit Algorithmen wie dem Dijkstra noch weitaus schneller lösen.