Kürzester Pfad

Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei unterschiedlichen Knoten $s,t \in V$ eines Graphen, welcher minimale Länge bezüglich einer Gewichtsfunktion $c : E \to \mathbb{R}$ hat. Haben die Kanten im Graphen alle das Gewicht 1, ist also $c_e \equiv 1 \; \forall e \in E$, so ist der kürzeste Pfad ein $s$-$t$-Pfad mit der geringstmöglichen Anzahl von Kanten zwischen $s$ und $t$.

In der Literatur wird das Problem oft als Shortest Path Problem bezeichnet.

Komplexität

Im Allgemeinen ist die Bestimmung eines kürzesten Pfades ein schweres Problem: Das Entscheidungsproblem

„Hat ein Graph einen $s$-$t$-Pfad der Länge $\leq C$?“

ist NP-vollständig, dementsprechend kann im Allgemeinen auch ein kürzester Pfad vermutlich nicht in Polynomialzeit gefunden werden. Hat ein Graph einen Hamiltonpfad, so ist dies ein kürzester $s$-$t$-Pfad bezüglich der Gewichtsfunktion $c(e) = -1 \; \forall e \in E$. Auch hier ist schon die Frage nach der Existenz eines solchen Pfades ein NP-vollständiges Problem.

In vielen Spezialfällen ist die Bestimmung kürzester Pfade in Polynomialzeit trotz der Komplexität des Problems möglich. Die wichtigste Einschränkung betrifft hier die Gewichtsfunktion:

konservative Gewichtsfunktion

Eine Gewichtsfunktion heißt konservativ für den Graphen $G$, wenn $c(C) = \sum_{e \in C} c(e) \geq 0$ für alle Zyklen $C$ von $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 weiterhin von der Zielfunktion zusätzlich sogar Nichtnegativität verlangt, also $c(e) \geq 0 \; \forall e \in E$ fordert, so lässt sich das Problem mit dem A*-Algorithmus oder dem Algorithmus von Dijkstra noch weitaus schneller lösen.

Variationen des Problems

Abgesehen von der Bestimmung des kürzesten $s$-$t$-Pfades gibt es noch einige weitere, jedoch sehr ähnliche Probleme:

Single-source shortest path (SSSP)

Diese Variante des Problems der kürzesten Pfade befasst sich mit der Problemstellung wie man die kürzesten Wege zwischen einem gegebenen Startknoten und allen übrigen Knoten eines Graphen berechnet. Für nichtnegative Gewichtsfunktionen lassen sich der Dijkstra-Algorithmus bzw der A*-Algorithmus leicht so anpassen, dass die kürzesten Wege zu allen Knoten des Graphs zu berechnen. Für beliebige konservative Gewichtsfunktionen berechnet der Bellman-Ford-Algorithmus andererseits stets auch die kürzesten Pfade zu allen anderen Knoten.

Single-destination shortest path

Ziel ist hier die Bestimmung des kürzesten Pfads zwischen einem Endknoten und allen anderen Knoten des Graphen. Dieses Problem kann durch eine Umkehrung der Kantenrichtungen als SSSP beschrieben werden.

All-pairs shortest path (APSP)

In dieser Variante des Problems geht es um die Bestimmung der kürzesten Pfade zwischen allen Knotenpaaren eines Graphen zu berechnen. Abhängig von der Gewichtsfunktion ist es effizienter, für jeden Knoten nacheinander das SSSP lösen oder jedoch spezialisierte Verfahren, wie etwa den Floyd-Warshall-Algorithmus oder den Min-Plus-Matrixmultiplikations-Algorithmus, die gleichzeitig für alle Paare kürzeste Pfade bestimmen, zu verwenden.

Beispiel

Beispielgraph

Im nebenstehend gegebenen Graphen ist ein kürzester Pfad zwischen den Knoten $D$ und $C$ der Pfad, welcher in $D$ startet, und über $B$ nach $C$ geht. Die Pfadkosten betragen hierbei $9+8=17$. Will man jedoch einen Pfad von $D$ nach $E$ finden, so ist der direkte Weg mit Kosten von $15$ nicht der kürzestmögliche Pfad, da der Weg von $D$ über $F$ nach $E$ nur Kosten von $14=8+6$ hat.

Formulierung als lineares Programm

Zur Bestimmung eines kürzesten Pfades lässt sich außerdem ein lineares Programm heranziehen. Man interpretiert in diesem Fall den Pfad als Fluss mit einem Flusswert von 1 auf den Kanten des Graphen. Die Bestimmung des kürzesten Pfades ist dann ein Spezialfall des Min-cost-flow-Problems. Die entsprechende Formulierung lautet:

$\begin{align} \min & \sum_{e \in E} c_e x_e \\ \text{so dass } & \forall \; v \in V\colon\; \sum_{e \in \operatorname{\delta^-}(v)} x_e - \sum_{e \in \operatorname{\delta^+}(v)} x_e = \begin{cases} -1,& \text{falls } v = s \\ 1,& \text{falls } v = t \\ 0,& \text{sonst } \end{cases} \\ & \forall \; e \in E\colon\; x_e \geq 0 \\ \end{align}$

Falls ein $s$-$t$-Pfad im gegebenen Graphen existiert, so hat das Programm eine zulässige Lösung. Das Programm ist allerdings unbeschränkt, wenn die Gewichtsfunktion nicht konservativ ist. In diesem Fall kann der Fluss nämlich entlang eines Zykels mit negativen Kosten beliebig weit erhöht werden. Andernfalls hat das Problem eine Optimallösung $x$, welche einem $0/1$-Vektor mit $|E|$ Einträgen entspricht. Die Menge $\{e \in E \,:\, x_e = 1 \}$ beschreibt dann einen kürzesten $s$-$t$-Pfad, der Zielfunktionswert des Programms entspricht der Länge des Pfades.

Knotenpotentiale

Es stellt sich heraus, dass die Dualisierung des obigen linearen Programms eine anschauliche Interpretation hat. Das duale Programm ist gegeben durch

$\begin{align} \max & y_t - y_s \\ \text{so dass } & \forall \; e=(u,v) \in E\colon\; y_v - y_u \leq c_e \;\; \end{align}$

Eine Lösung $y$ des dualen Programms nennt man ein Knotenpotential. Man sieht leicht, dass für jede Lösung $(y_v)_{v \in V}$ der Vektor $(y_v + \delta)_{v \in V}$ ebenfalls eine Lösung ist, wobei man $\delta \in \mathbb{R}$ beliebig wählen kann. Man setzt in der Regel den Wert von $\delta$ so, dass $y_s = 0$. Die Zielfunktion ist dann gegeben durch $\max \; y_t$.

Ist $P$ ein beliebiger Pfad zwischen $s$ und einem Knoten $w \neq s$, so lässt sich die Länge des Pfades wie folgt abschätzen:

$c(P) = \sum_{e \in P} c_e \geq \sum_{e=(u,v) \in P} y_v - y_u = y_w$

Das Potential eines jeden Knotens ist also eine untere Schranke für die Länge eines Pfades. Eine Optimallösung des dualen Programms findet man, wenn man das Potential eines Knotens $w \neq s$ als die Länge des kürzesten $s$-$w$-Pfades bezüglich der Zielfunktion $c$ setzt.

Anwendungen

Siehe auch: Pathfinding

Algorithmen, die einen kürzesten Pfad berechnen, finden häufig Anwendung in der Berechnung von Reiserouten. So kann zum Beispiel die Entfernung zwischen zwei Städten berechnet werden. Dabei sind die Städte die Knoten des Graphen und die Straßen die Kanten.

Kürzeste Wege mit Nebenbedingungen

Eine Varallgemeinerung des Problems erhält man, wenn man nur $s$-$t$-Pfade $P$ betrachtet, die der zusätzlichen Ungleichung $\sum_{e \in P} u_e \leq U$ gehorchen. Dabei ist $u : E \to \mathbb{R}_+$ eine weitere Gewichtsfunktion und $U$ eine reelle Zahl.

Das resultierende Constrained Shortest Path Problem ist dann auch für konservative bzw. nichtnegative Zielfunktionen NP-schwer, siehe .

Literatur

•  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung. 2. Auflage. 2007. ISBN 978-3-486-58262-8
• H. C. Joksch (1966). The shortest route problem with constraints. J. Math. Anal. Appl. 14, Seite 191-197