Graph Theory37 sections · 1633 units
Open in Course

Quiz: SPFA Worst Case

Knowledge check

Check Your Understanding

SPFA processes only nodes whose distances changed, using a queue. In the worst case, what is its time complexity?

  1. A.O(V+E)O(V + E), same as BFS
  2. B.O(V⋅E)O(V \cdot E), same as standard Bellman-Ford
  3. C.O(Elog⁡V)O(E \log V), same as Dijkstra
  4. D.O(V2log⁡V)O(V^2 \log V)
Start the roadmap to answer the quizzes and solve the challenges