Kürzester Pfad
aus Wikipedia, der freien Enzyklopädie
Unter einem kürzesten Pfad versteht man in der Graphtheorie einen Pfad zwischen zwei Knoten u und v, 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.
[Bearbeiten] Beispiele
Im oben gegebenen Graphen ist ein kürzester Pfad zwischen den Knoten D und C der Pfad, welcher in D startet, und über B nach C geht. Die Pfadkosten betragen hierbei 9 + 8 = 17. Will man jedoch einen Pfad von D nach E finden, so ist der direkte Weg mit Kosten von 15 nicht der kürzestmögliche Pfad, da der Weg von D über F nach E nur Kosten 14 = 8 + 6 hat.
Um kürzeste Pfade in Graphen zu berechnen kann man zum Beispiel folgende Algorithmen verwenden:
[Bearbeiten] Literatur
- Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 2001, ISBN 0262531968
