Dijkstra's algorithm requires that
Athe graph is a tree, not a general graph
Bedge weights are integers, not floating-point
Cthe graph has fewer than 1000 vertices
Devery edge weight is non-negative
Answer & Solution
Correct answer: D. every edge weight is non-negative
Dijkstra commits to a vertex's distance when extracted from the priority queue and assumes no future relaxation can lower it. Negative edges break this assumption: a longer-but-cheaper path could appear after the commit. Use Bellman-Ford for graphs with negative edges. Dijkstra works on general graphs, integers or floats, any vertex count.
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