Datenstrukturen
Für die Implementierung des Dijkstra-Algorithmus benötigen wir Datenstrukturen, um den Graphen, die Distanz Dist(v) und den Vorgänger Vor(v) eines Knotens sowie die Front (Menge U) effizient zu verwalten. Der Graph kann z.B. in einer Adjazenzliste Tail [1, ..., n] abgespeichert werden: Tail(i) zeigt auf den Beginn einer verketteten Liste, die die Endknoten j und Kosten von Kanten (i, j) in E enthält.
Die Distanz und der Vorgänger eines Knotens können in Felder Dist[1 ... n] und Vor[1 ... n] abgelegt werden.
Die Verwaltung der Front verlangt eine Datenstruktur, die die folgenden Operationen unterstützt.
- finde Minimum
- lösche Minimum
- füge ein
- verringere Inhalt eines gegebenen Elements.
 |
 |
 |