Shortest paths with negative weights Dijkstra's algorithm can return a wrong answer on a graph that has negative edge weights. What exactly goes wrong?

Question

Accepted Answer

A vertex can be removed from the priority queue and its distance treated as final before a cheaper path to it is discovered.

Answer

It relaxes some edges twice and double-counts their weight.

Answer

The priority queue cannot hold a negative key.

Answer

It reports a negative cycle even when the graph has none.

Answer

The algorithm never terminates, because the estimates keep decreasing.

Crowdly

Shortest paths with negative weights Dijkstra's algorithm can return a wrong ans...

Хочете миттєвий доступ до всіх перевірених відповідей на learning.monash.edu?