Das Problem

Kürzeste Wege

Viele Wege führen vom Kreuz Frankenthal zum Kreuz Heidelberg. Aber welcher dieser Wege ist der kürzeste?

Diese Frage, lässt sich leicht zu einem allgemeinen Graphenproblem verallgemeinern:

Gegeben ist ein (gerichteter oder ungerichtetet, gewichteter) Graph. Gegeben ist zusätzlich ein Start- und ein Zielknoten. Welcher Weg des Graphen vom Startknoten zum Zielknoten ist der kürzeste. Dabei soll die Länge des Weges durch die Summe der Gewichte der Kanten längs des Weges erfasst werden.

Ziel der folgenden Abschnitte ist es, einen Algorithmus zur Lösung dieses Problems zu entwickeln. Wir werden im nächsten Abschnitt erst einmal nicht-gewichtete Graphen betrachten. Die hier erzielten Ergebnisse können dann relativ leicht auf gewichtete Graphen übertragen werden.