Ein
kürzester Pfad ist in der
Graphentheorie ein
Pfad zwischen zwei unterschiedlichen
Knoten eines
Graphen, welcher minimale Länge bezüglich einer
Gewichtsfunktion hat. Haben die
Kanten im Graphen alle das Gewicht 1, ist also , so ist der kürzeste Pfad ein
–
-Pfad mit der geringstmöglichen Anzahl von Kanten zwischen
und
.