Question discussion

Which shortest-path algorithm can detect a negative-weight cycle that is reachable from the source vertex?

2102Medium DSSSB TGT Computer Science 0 replies 2 views

ADijkstra's algorithm
BBellman–Ford algorithm
CPrim's algorithm
DKruskal's algorithm

Correct answer: B

Explanation

Bellman–Ford relaxes all edges V − 1 times and a further improvement on the V-th pass reveals a negative cycle; Dijkstra's algorithm fails with negative edges.

Join the discussion Report an error

Discussion 0

Nobody has replied yet. Start the discussion!