Kürzester Pfad

Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten $u$ und $v$, 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.

Es sollten folgende Unterscheidungen vorgenommen werden.

• single-pair shortest path. Der kürzeste Pfad zwischen zwei unterschiedlichen Knoten.
• single-source shortest path (SSSP). Der kürzeste Pfad zwischen einem Startknoten und allen anderen Knoten des Graphen.
• single-destination shortest path. Der kürzeste Pfad zwischen einem Endknoten und allen anderen Knoten des Graphen. Dies ist eine Umkehrung des SSSP und kann durch eine Umkehrung der Kantenrichtungen erreicht werden.
• all-pairs shortest path (APSP). Der kürzeste Pfad, von jedem Knoten im Graph, zu jedem anderen Knoten.

Anwendung

→ siehe: Pathfinding

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

Beispiele

Beispielgraph

Im oben 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 $14=8+6$ hat.

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

• A*-Algorithmus
• Algorithmus von Dijkstra
• Bellman-Ford-Algorithmus
• Floyd-Warshall-Algorithmus
• Johnson-Algorithmus (Graphentheorie)

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. → siehe: SSSP mit Ressourcen

Literatur

• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 2001, ISBN 0262531968
• Bernhard Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. Springer, 2008, ISBN 978-3-540-71844-4