Gerichteter, kantengewichteter Graph – die Zahlen sind die Gewichte, auch negative
queue – links wird entnommen, rechts eingereiht (Zahl darunter: Durchlauf):
relax(v) läuft in der Warteschlange (onQ) Weg von s bekannt Kante in edgeTo[] Kante wird relaxiert nicht auswählbar negativer Zyklus · distTo durchgestrichen: nicht länger gültig Ausgabe: pathTo(t)
Java (eigene Fassung, nach Algorithmus 4.11, Listing 4.36 bis 4.38)

    

      
Ausgabe von main()

      
Protokoll