Laufzeit

arrows

exponentiell viele Relaxations-Schritte:

$\begin{tikzpicture}[node distance=5cm,auto,>=stealth,thick] \node (s) {s}; \no... ...t] node {0} (q); \path[->] (q) edge [bend left] node {0} (t); \end{tikzpicture}$

besser:

Bellman-Ford (polynomiell)
for i mathend000# from 1 mathend000# to | V| mathend000#: jede Kante e∈E mathend000# einmal entspannen
dann testen, ob alle Kanten entspannt sind.
(d. h. d (j)≥d (i) + w_{i, j} mathend000#)
Wenn nein, dann existiert negativer Kreis. (Beweis?)
Dijkstra (schneller, aber nur bei Gewichten ≥ 0 mathend000# korrekt)

2014-03-31