(single-source shortest paths)
- Eingabe:
- gerichteter Graph G = (V, E)
- Kantengewichte
w : E
- Startknoten s V
- Ausgabe:
Funktion
D : V mit
x V : D(x) = minimales Gewicht eines Pfades von s nach x
äquivalent: Eingabe ist Matrix
w : V×V { + }
bei (von s erreichbaren) negativen Kreisen
gibt es x mit
D(x) = -
2009-06-22