Which of the following algorithms is used to find the shortest path in a graph with negative weights?

Answer:

Explanation:

The Bellman-Ford algorithm is used to find the shortest path in graphs with negative weights. Unlike Dijkstra’s algorithm, Bellman-Ford can handle negative weight edges and detect negative weight cycles.

Bellman-Ford works by relaxing edges repeatedly, allowing it to update the shortest path distances from the source vertex to all other vertices. If a negative weight cycle is detected, the algorithm reports that no shortest path exists.

Although Bellman-Ford has a higher time complexity of O(V * E), it is more versatile than Dijkstra’s algorithm, which is limited to graphs with non-negative weights.