Question

Which algorithm is used for finding the shortest path in a weighted graph with negative edges?

• A. Bellman-Ford
• B. Dijkstra’s
• C. Kruskal’s
• D. Prim’s

Hint:

Choose Bellman-Ford for graphs with negative weights; Dijkstra’s for non-negative weights.

Answer 1

The Correct Option is A

- Bellman-Ford algorithm handles graphs with negative edge weights and detects negative cycles, with time complexity $O(VE)$.
- Dijkstra’s algorithm fails with negative weights, requiring non-negative edges.
- Kruskal’s and Prim’s are for minimum spanning trees, not shortest paths.
Option (1) is correct.