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 ( 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 ;
der Startknoten erhält die vorläufige Disstanz 0.
Jeweils der billigste Knoten aus der Menge der vorläufig markierten Knoten
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.
Source: Dijkstra.java JavaDoc: Dijkstra.html