Bellman–Ford

Finds shortest paths from one source, relaxing every edge V−1 times rather than settling vertices greedily. That makes it slower than Dijkstra but correct with negative edge weights, and one extra pass at the end detects negative cycles — which Dijkstra cannot do at all.

Best

O(V+E)

Average

O(VE)

Worst

O(VE)

Space

O(V)