Kürzeste Wege

Das Problem der kürzesten Wege besteht darin, in einem gerichteten, mit nichtnegativen Kosten gewichteten Graphen die kürzesten Wege von einem Startknoten zu allen anderen Knoten auszurechnen (single source shortest paths).

Der Algorithmus von Dijkstra verwendet dabei eine Priority-Queue ($\approx$ Heap aus Kapitel 7), welche die vorläufige Distanz eines Weges vom Startknoten zu einem Zielknoten in Form eines mit dieser Distanz bewerteten Knotens speichert.

Zu Beginn haben alle Knoten die vorläufige Distanz $\infty$; der Startknoten erhält die endgültige Distanz 0. Jeweils der billigste Knoten aus der Prioritäts-Schlange kann seine endgültige Distanz erhalten und fügt ggf. die durch ihn verkürzten vorläufigen Distanzen zu seinen Nachbarn in Form von Knoten in die Schlange ein. Weil die Priority-Queue die Kosten der in ihr gespeicherten Wege nicht verringern kann, werden Wege, deren Kosten sich verringert haben, als neue Knoten eingefügt und die Schlange enthält daher für manche Knoten Mehrfacheinträge mit unterschiedlich teuren Distanzen. Solche Einträge können nach dem Entfernen aus der Schlange ignoriert werden, wenn der Knoten inzwischen als besucht (seen) markiert wurde.

Single-Source-Shortest-Path:
Grau gefärbt sind bereits markierte Knoten

Source: Dijkstra.java     JavaDoc: Dijkstra.html