Kürzeste Wege in Graphen

(single-source shortest paths)

• Eingabe:
  • gerichteter Graph G = (V, E)
  • Kantengewichte w : E→$\mathbb {R}$
  • Startknoten s∈V
• Ausgabe: Funktion D : V→$\mathbb {R}$ mit ∀x∈V : D(x) = minimales Gewicht eines Pfades von s nach x

äquivalent: Eingabe ist Matrix w : V×V→$\mathbb {R}$∪{ + ∞}

bei (von s erreichbaren) negativen Kreisen gibt es x mit D(x) = - ∞