Kürzester Pfad

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 .