Kürzeste Wege in Graphen

(single-source shortest paths)

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

äquivalent: Eingabe ist Matrix w : V×V$\to$$\mathbb {R}$ $\cup$ { + $\infty$}

bei (von s erreichbaren) negativen Kreisen gibt es x mit D(x) = - $\infty$