Question

Ahuja et al. found that using a van Emde Boas tree reduces the complexity of this problem to “big O of m log log C” when certain values are bounded by C. For hidden Markov models, the Viterbi algorithm essentially solves this problem with probabilistic weights added. Fredman and Tarjan used Fibonacci heaps to find the asymptotically fastest known algorithm for one form of this problem, improving on Johnson’s (10[1])algorithm. The Floyd–Warshall algorithm solves this problem for multiple sources. (-5[1])A priority queue is typically used to store unvisited items in a “big O (-5[1])of (10[1]-5[1])m log n” (-5[1])algorithm for this task. The Bellman–Ford algorithm works for this problem even if edge weights are negative, unlike Dijkstra’s algorithm. For 10 (10[1])points, name this problem of finding the minimum-distance route between (10[1])two vertices of a graph. ■END■ (10[3]0[2])

ANSWER: shortest path problem [accept pathfinding]
<Other Science>
= Average correct buzz position

Back to tossups

Summary

2024 ACF Regionals @ Berkeley01/27/2024Y1100%0%0%71.00
2024 ACF Regionals @ JMU01/27/2024Y1100%0%0%134.00
2024 ACF Regionals @ JMU01/27/2024Y1100%0%0%83.00
2024 ACF Regionals @ Nebraska01/27/2024Y683%0%33%118.80
2024 ACF Regionals @ Imperial01/27/2024Y888%0%50%115.57
2024 ACF Regionals @ Vanderbilt01/27/2024Y1100%0%0%116.00
2024 ACF Regionals @ MIT01/27/2024Y367%0%100%134.00

Buzzes

PlayerTeamOpponentBuzz PositionValue
Omer KeskinOxford AImperial A6810
Linus LuuCambridge CDurham B78-5
Andrew FisherSheffieldKiel92-5
Carlos DoebeliImperial BCambridge A93-5
Matt SheldonOxford COxford B9310
Parth JagtapEdinburghWarwick96-5
Michael KohnDurham ACambridge B11810
Thomas HartWarwickEdinburgh12810
Maxwell YeCambridge AImperial B13410
Aisling SkeetDurham BCambridge C13410
Kevin FlanaganBristolKCL13410
Nick PruittKCLBristol1340
Ian DewanKielSheffield1340