Gerichteter, kantengewichteter Graph – die Zahlen sind die Gewichte
IndexMinPQ pq – oben der Heap (pq[Position] = Knoten, Schlüssel = distTo), unten qp[] (Knoten → Position, −1 = nicht drin):
relax(v) läuft Abstand endgültig in pq, rot: bisher beste letzte Kante Kante im Baum der kürzesten Pfade Kante wird relaxiert Ausgabe: pathTo(t)
Java (eigene Fassung, nach Algorithmus 4.9, Listing 4.32)

    

      
Ausgabe von main()

      
Protokoll