On a graph with some negative-weight edges, Dijkstra's algorithm may
Astill work but with double the running time
Balways return the correct answer; the requirement is only a convention
Cloop forever in an infinite recursion
Dreturn wrong distances; it commits to d[u] before later paths could lower it
Answer & Solution
Correct answer: D. return wrong distances; it commits to d[u] before later paths could lower it
When Dijkstra extracts u from the priority queue, it assumes no future relaxation will lower d[u]. With a negative edge, a longer path through some other vertex could later decrease d[u] — but Dijkstra has already committed. The result: incorrect distances. Bellman-Ford handles negative edges (at slower speed); use it when needed.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for