Question

Which statement correctly explains why Dijkstra's algorithm produces incorrect shortest-path results on graphs containing negative edge weights, even when no negative-weight cycle exists?

Q: Answer-Which statement correctly explains why Dijkstra's algorithm produces incorrect shortest-path results...

Dijkstras correctness relies on the greedy assumption that once a vertex is removed from the priority queue with its current shortest known distance, that distance is final because all remaining edges are non-negative and cannot produce a shorter path later. A negative edge encountered after a vertex is finalized can create a shorter path that the algorithm never reconsiders, producing an incorrect result, even without any negative cycle being present.

A Because Dijkstra's priority queue implementation cannot store or compare negative numeric keys

B Because negative edge weights cause the algorithm's internal graph representation to become cyclic, breaking termination

C Because Dijkstra greedily finalizes a vertex's shortest distance the moment it is dequeued, assuming no later-discovered path could be shorter — an assumption negative edges can violate

D Because negative weights make previously reachable vertices appear disconnected to the algorithm, causing them to be skipped entirely

E Because Dijkstra requires the cumulative weight of every path to remain positive before it can initialize its distance array

Practice Next

Which statement correctly explains why Dijkstra's algorithm produces incorrect shortest-path results on graphs containing negative edge weights, even when no negative-weight cycle exists?

Detailed Solution

More Data Structure Questions

Hey! Ask a query

Please Register/Login

RBI Grade B 2026 Phase 1 Memory Based Paper