Which algorithm solves single-source shortest paths with negative edge weights (assuming no negative cycles) and what is its time complexity?

• A. Dijkstra, O(E log V)
• B. Floyd-Warshall, O(V^3)
• C. Bellman-Ford, O(VE)
• D. SPFA, O(VE)

Answer: (C)

When negative edge weights are allowed (but no negative cycles), you need an algorithm that can update distances even when paths can decrease along the way. Bellman-Ford does this by relaxing every edge repeatedly, across V-1 passes. Since any simple path has at most V-1 edges, after these passes the shortest distances from the source are determined. It also lets you detect a reachable negative cycle with one extra pass, if any distance can still be improved. The time complexity is O(VE) because you perform E relaxations in each of V-1 iterations. In comparison, methods like Dijkstra assume non-negative weights and can fail with negatives (O(E log V)), Floyd-Warshall computes all-pairs shortest paths in O(V^3), and SPFA is a practical optimization with worst-case O(VE). So the best fit for single-source shortest paths with negative weights (no negative cycles) is Bellman-Ford, with time complexity O(VE).