alleryStart learning →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.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.