Kürzester Pfad

Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei unterschiedlichen Knoten ${\displaystyle s,t\in V}$ eines Graphen, welcher minimale Länge bezüglich einer Kantengewichtsfunktion ${\displaystyle c\colon E\to \mathbb {R} }$ hat. Haben die Kanten im Graphen alle das Gewicht 1, ist also ${\displaystyle c(e)=1}$ für alle Kanten ${\displaystyle e\in E}$, so ist der kürzeste Pfad ein ${\displaystyle s}$–${\displaystyle t}$-Pfad mit der geringstmöglichen Anzahl von Kanten zwischen ${\displaystyle s}$ und ${\displaystyle t}$.

Die Aufgabe für einen gegebenen Graph einen kürzesten Pfad zu berechnen, ist ein Optimierungsproblem und wird in der Literatur oft als Shortest Path Problem oder Single-Source Shortest Path (SSSP) bezeichnet.

1. ↑ 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)