Bellmann-Ford Algorithmus

Ist ein Kürzeste Wege Algorithmus, der von einem Startknoten $s$ aus die kürzesten Wege zu allen anderen Knoten berechnet. Dabei dürfen die Kantengewichte beliebig sein (also auch negativ). Allerdings darf es keinen negativen Zyklus bzw Kreis geben.

Laufzeit

ist $\mathcal{O}(n\cdot m)$. Will man die kürzesten Wege von jedem Knoten aus zu jedem anderen Knoten haben ist die Laufzeit entsprechen $\mathcal{O}(n^2\cdot m)$#