Kürzeste Wege in Graphen

(single-source shortest paths)

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

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

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