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 bezeichnet.