Kürzester Pfad

Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei Knoten, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den wenigsten Knoten. Sollten die Kanten jedoch unterschiedliche Kantengewichte haben, so ist ein kürzester Pfad nicht notwendigerweise der Pfad, der durch die wenigsten Knoten verläuft.

Definitionen

Single-pair shortest path

Der kürzeste Pfad zwischen zwei unterschiedlichen, fest vorgegebenen Knoten.

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. Bei einer guten Implementierung ist für diesen Fall der Algorithmus von Dijkstra schneller als der von Bellmann und Ford.

Single-destination shortest path

Der kürzeste Pfad zwischen einem Endknoten und allen anderen Knoten des Graphen. Dieser kann durch eine Umkehrung der Kantenrichtungen als SSSP beschrieben werden.

All-pairs shortest path (APSP)

Diese Variante des Problems der kürzesten Pfade befasst sich mit der Problemstellung alle kürzesten Pfade zwischen zwei Knotenpaaren eines Graphen zu berechnen. Sie tritt z.B. auf, wenn für eine Straßenkarte eine Tabelle mit den kürzesten Entfernungen zwischen alle Paaren von Städten hergestellt werden soll. Das Problem könnte gelöst werden indem man für jeden Knoten einen single-source shortest path Algorithmus laufen lässt. Allerdings kann das Problem schneller gelöst werden. z.B. mit Hilfe des Floyd-Warshall-Algorithmus.

Algorithmen

Um kürzeste Pfade in Graphen zu berechnen kann man zum Beispiel folgende Algorithmen verwenden:

• A*-Algorithmus
• Dijkstra-Algorithmus
• Bellman-Ford-Algorithmus
• Algorithmus von Floyd und Warshall
• Johnson-Algorithmus

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.

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

Wenn jede Kante nicht nur Kosten hat, sondern auch Ressourcen, dann ist das Problem NP-schwer, also nicht mehr polynomiell lösbar.

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
• 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).