Algorithms and Data Structures · Middle · Question 28 of 75
Why does BFS find the shortest path in an unweighted graph?
- 1It always follows the edge with the smallest weight
- 2It explores every possible path before deciding
- ✓Correct answer: It visits vertices in order of their distance from the start
Explanation
The queue processes all vertices at distance 1, then distance 2, and so on. The first time BFS reaches a vertex, it does so by a shortest path. With weighted edges you need Dijkstra instead.