Dijkstra's algorithm may not terminate if the graph contains negative-weight edges

a) False. It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results.

b) True. It may not terminate and if it does after |E| relaxations and |V|+|E| priority queue operations, it may produce incorrect results.

c) True. It can never terminate as the negative-weight edges continuously reduce the shortest path weight even after |E| relaxations and |V|+|E| priority queue operations.

d) False. It can surely terminate as long as the negative-weight edges are not considered for the shortest path weight calculation among those |E| relaxations and |V|+|E| priority queue operations

Question

Computers & Technology

Wells

19 February, 12:32

Dijkstra's algorithm may not terminate if the graph contains negative-weight edges

a) False. It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results.

b) True. It may not terminate and if it does after |E| relaxations and |V|+|E| priority queue operations, it may produce incorrect results.

c) True. It can never terminate as the negative-weight edges continuously reduce the shortest path weight even after |E| relaxations and |V|+|E| priority queue operations.

d) False. It can surely terminate as long as the negative-weight edges are not considered for the shortest path weight calculation among those |E| relaxations and |V|+|E| priority queue operations

+5

Answers (1)

Know the Answer?

Ty Dunlap · Answer 1

The answer is letter A.

Explanation:

False. It always terminates after |E| relaxations and |V|+|E| priority queue operations, but may produce incorrect results. Because the negative edges can reduce the distance, you may find a shorter distance, however since the node will be deleted it won't be uptaded. The nodes will be deleted from the priority queue.