Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei unterschiedlichen Knoten eines Graphen, welcher minimale Länge bezüglich einer Kantengewichtsfunktion hat. Haben die Kanten im Graphen alle das Gewicht 1, ist also für alle Kanten , so ist der kürzeste Pfad ein –-Pfad mit der geringstmöglichen Anzahl von Kanten zwischen und .
In der Literatur wird das Problem oft als Shortest Path Problem bezeichnet.
Komplexität Bearbeiten
Die Komplexität hängt maßgeblich von der Art der Gewichtsfunktion ab und davon, ob Pfade oder Kantenzüge betrachtet werden. In Kantenzüge können sich Knoten und Kanten wiederholen, während Pfade keinen Knoten doppelt verwenden. Man unterscheidet drei Arten von Gewichtsfunktionen:
- Gewichtsfunktionen ohne negative Gewichte;
- Konservative Gewichtsfunktion: Eine Gewichtsfunktion heißt konservativ für den Graphen , wenn für alle Zyklen von ;
- Gewichtsfunktionen mit beliebigen Gewichten.
Die genaue Problemformulierung ist entscheidend um die Komplexitätsfrage beantworten zu können.
Die Literatur beschränkt sich meistens auf nichtnegative Gewichte oder konservative Gewichtsfunktion. Mit einer dieser Zusatzforderungen ist jeder kürzeste Pfad automatisch ein kürzester Kantenzug und deswegen wird in der Literatur diese Unterscheidung oft nicht gemacht.
Im Gegensatz zum Problem des kürzesten Pfades, ist das Problem des längsten Pfades sogar für ungewichtete Graphen NP-schwer.
Variationen des Problems Bearbeiten
Abgesehen von der Bestimmung eines kürzesten –-Pfades gibt es noch einige weitere, jedoch sehr ähnliche Probleme:
Single-source shortest path (SSSP) Bearbeiten
Diese Variante befasst sich mit dem Problem, 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 anpassen, um 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 (SDSP) Bearbeiten
Ziel ist hier die Bestimmung eines kürzesten Pfades 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) Bearbeiten
In dieser Variante geht es um die Bestimmung der kürzesten Pfade zwischen allen Knotenpaaren eines Graphen. 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 zu verwenden, die gleichzeitig für alle Paare kürzeste Pfade bestimmen.
Beispiel Bearbeiten
Im nebenstehend gegebenen Graphen ist ein kürzester Pfad zwischen den Knoten und der Pfad, welcher in startet, und über nach geht. Die Pfadkosten betragen hierbei . Will man jedoch einen Pfad von nach finden, so ist der direkte Weg mit Kosten von nicht der kürzestmögliche Pfad, da der Weg von über nach nur Kosten von hat.
Formulierung als lineares Programm Bearbeiten
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:
Falls ein –-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 , welche einem -Vektor mit Einträgen entspricht. Die Menge beschreibt dann einen kürzesten –-Pfad, der Zielfunktionswert des Programms entspricht der Länge des Pfades.
Knotenpotentiale Bearbeiten
Es stellt sich heraus, dass die Dualisierung des obigen linearen Programms eine anschauliche Interpretation hat. Das duale Programm ist gegeben durch
Eine Lösung des dualen Programms nennt man ein Knotenpotential. Man sieht leicht, dass für jede Lösung der Vektor ebenfalls eine Lösung ist, wobei man beliebig wählen kann. Man setzt in der Regel den Wert von so, dass . Die Zielfunktion ist dann gegeben durch .
Ist ein beliebiger Pfad zwischen und einem Knoten , so lässt sich die Länge des Pfades wie folgt abschätzen:
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 als die Länge des kürzesten –-Pfades bezüglich der Zielfunktion setzt.
Anwendungen Bearbeiten
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. Verschiedene Algorithmen sind in der freien Python-Bibliothek NetworkX implementiert.
Kürzeste Wege mit Nebenbedingungen Bearbeiten
Eine Verallgemeinerung des Problems erhält man, wenn man nur –-Pfade betrachtet, die der zusätzlichen Ungleichung gehorchen. Dabei ist eine weitere Gewichtsfunktion und eine reelle Zahl.
Das resultierende Constrained Shortest Path Problem ist dann auch für konservative bzw. nichtnegative Zielfunktionen NP-schwer, siehe H. C. Joksch (1966).
Literatur Bearbeiten
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 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
Einzelnachweise Bearbeiten
- Bernhard Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4th edition. Springer, Berlin u. a. 2008, ISBN 978-3-540-71844-4 (Algorithms and Combinatorics 21)
- Algorithms - Shortest Paths. In: NetworkX 2.2 documentation. Abgerufen am 24. Oktober 2018 (englisch).
- H. C. Joksch (1966)