- Non-negative weights: Dijkstra’s algorithm — single source to all vertices, O((V + E) log V) with a binary heap.
- Negative edge weights: Bellman–Ford algorithm — relaxes every edge V − 1 times, O(V·E); one more pass detects a negative cycle, in which case shortest paths are undefined.
Dijkstra can fail with negative edges because it finalises a vertex’s distance too early. (For all pairs: Floyd–Warshall, or Johnson’s algorithm with negative edges.)
— rhs