Das kürzeste-Wege-Problem             Gliederung Einige Begriffe der Graphentheorie Als Abstraktion eines Verkehrsnetzes, das aus Bahnhöfen, Städten oder Kreuzungen und Gleis- oder Straßenverbindungen besteht, verwenden wir Graphen. Ein gerichteter Graph besteht aus einer (endlichen) Menge V von Knoten und einer (endlichen) Menge E von Kanten, die je zwei Knoten miteinander verbinden. Wir können daher E mit einer Teilmenge { (v,w) aus V } identifizieren. Zusätzlich seien nichtnegative ''Entfernungen'' c(v,w) >= 0  gegeben und ein Startknoten s aus V ausgezeichnet. Wir veranschaulichen uns Graphen, indem wir die Knoten als kleine Kreise zeichnen und die Kanten (v,w) als Pfeile, die einen Knoten v mit einem Knoten w verbinden. Beispiel Unter einem Weg   P   von einem Knoten   v   zu einem anderen Knoten   w   verstehen wir eine Folge   v0, v1, ... , vk   von Knoten, so daß   v0 = v,  vk = w   und   (vi, vi+1) Kanten aus   E  sind. Der Weg hat die Länge c(P) = c(v0,v1) + c(v1, v2) + ... + c(vk-1,vk). Beispiel Das kürzeste-Weg-Problem besteht darin, Wege kürzester Länge von s zu allen anderen Knoten zu bestimmen. Das folgende Verfahren von Dijkstra wird uns eine Lösung des kürzeste-Weg-Problems liefern. Dijkstra-Algorithmus