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

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).

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).