Kürzester Pfad

Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten  und , welcher minimale Länge hat. Haben die Kante 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.
Mehr unter Wikipedia.org...