Dijkstra's algorithm requires…
Options
- A directed acyclic graph (DAG)
- Edge weights that are not negative (Correct option)
- A graph without weights on its edges
- An adjacency matrix as the representation
Answer
Non-negative edge weights
Why
Dijkstra finds shortest paths when edges have weights (distances, costs). It always expands the closest unvisited node next (using a min-heap) and treats its distance as final.
That 'final' decision is only correct if no edge can make a path shorter later, i.e. no negative weights.
With negative weights use Bellman-Ford. Complexity with a heap: O((V + E) log V).
Remember
Dijkstra = weighted shortest path, no negative edges.