OBI Practice Questions - Olimpíada Brasileira De Informática Exam

Access More Questions

In a directed graph where every edge weight is either 0 or 1, which algorithm finds the single-source shortest path to all vertices in O(V + E) time without the logarithmic overhead of standard Dijkstra?

0-1 BFS using a double-ended queue (std::deque), pushing 0-weight edges to the front and 1-weight edges to the back Standard Breadth-First Search (BFS) using a single FIFO queue, inserting all relaxed vertices at the back regardless of weight Bellman-Ford algorithm executed for exactly 2 full iterations across all edges Floyd-Warshall algorithm restricted to vertices with incident 0-weight edges

Correct Answer:

0-1 BFS using a double-ended queue (std::deque), pushing 0-weight edges to the front and 1-weight edges to the back

Access more questions from this quiz

Continue to OBI Practice Questions - Olimpíada Brasileira de Informática Exam for more practice questions and the full quiz experience.

Access More Questions