Question

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

Answer 1

The answer is letter A.

Step-by-step 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.