Algorithms and Data Structures · Middle · Question 58 of 75
What does Dijkstra's algorithm compute?
- ✓Correct answer: Shortest paths from one vertex when weights are non-negative
- 2The minimum spanning tree of a weighted graph
- 3Shortest paths in any graph, including negative weights
Explanation
It repeatedly takes the unvisited vertex with the smallest known distance (from a priority queue) and relaxes its edges. With a binary heap it runs in O((V + E) log V). Negative weights break it.