VietMX Staff asked 3 years ago
Problem
What is the difference between Dijkstra’s and BFS? And then why are the time complexities of these algorithms so different?
- Breadth-first search is just Dijkstra’s algorithm with all edge weights equal to 1.
- BFS basically just expands the search by one “step” (link, edge, whatever you want to call it in your application) on every iteration, which happens to have the effect of finding the smallest number of steps it takes to get to any given node from your source (“root”)
- Breadth-first search can be viewed as a special-case of Dijkstra’s algorithm on unweighted graphs, where the priority queue degenerates into a FIFO queue.
- Operations on a regular queue are
O(1). - BFS runs in
O(E+V).
- Dijkstra’s algorithm is conceptually breadth-first search that respects edge costs.
- For example, in routing the distances (or weights) could be assigned by speed, cost, preference, etc.
- Dijkstra’s uses a priority queue data structure to keep track of the frontier of unvisited nodes.
- Operations on a priority queue are
O(log n). - Dijkstra’s runs in
O((V+E)*log(V))
The process for exploring the graph is structurally the same in both cases.
