Dijkstra’s algorithm - 2025 NAFTA

Packet 4: Bonus 15

A 2025 result from Duan et al. claims to have disproven the conjectured optimality of this algorithm. For 10 points each:

[10m] Name this algorithm that maintains and updates a set of “frontier” elements in a priority queue. This algorithm is extended by an algorithm that additionally filters elements using an admissible heuristic function.

ANSWER: Dijkstra’s algorithm (The extension is A*.)

[10e] Dijkstra’s algorithm accomplishes this task on non-negative edge-weight graphs.

ANSWER: shortest path finding [or shortest path; accept descriptions of finding the shortest path between two nodes or vertices of a graph]

[10h] This algorithm extends Dijkstra’s algorithm to negative edge weights by reweighting each edge to make them all positive, using the Bellman–Ford algorithm to find paths, undoing the reweighting, and then running Dijkstra’s algorithm.

ANSWER: Johnson’s algorithm

<SL, Other Science (Computer Science)> | NAFTA-Packet-4

Heard	PPB	E %	M %	H %
37	14.05	97%	43%	0%

Back to bonuses

Conversion

Team	Opponent	Part 1	Part 2	Total	Parts
1000000 Delinquents	In the Mood for Transportation Equipment	0	10	10	E
Ana Pauker? I hardly know her!	Georgia Tech 𓂈𓆉𓃡	10	10	20	ME
BHSU	The tram is not in service; please use the moving walkway.	0	10	10	E
Berkeley A	Team 7	10	10	20	ME
Capital One in the Twenty-First Century	The Fire Neg Time	10	10	20	ME
Chicago !A	(give me an) ANSWER: die for baseball	0	10	10	E
Contessa Dora	Maryland F♯ A♯ ∞	10	10	20	ME
Copán Seethe	It's something unpredictable/that in the end is right/please refrain from e-mailing my wife	0	10	10	E
Dielectrical Materialism	Vacuous Tortoise	10	10	20	ME
Dour Straits	A Neg of Beauty is a Joy Forever	0	10	10	E
Execute Order 6 7	Invective Against Swans	0	10	10	E
H Charlson's Washed Up Scrubs	The Third Time when she was Given to Answer the Hard and the Easy, and Answered Only the Easy	0	10	10	E
Habitat 67	The "C" Team	10	10	20	ME
I fear not the man who has reviewed 10000 cards once, but I fear the man who has reviewed one card 10000 times	Strange Case of Dr. Joker and Mr. Pennywise	10	10	20	ME
Indiana	Quebecois Olga Tokarczuk be like 'freins de jacob interdits'	0	10	10	E
Licence to Bill	I'm just here (being trivia club president) so I won't get fined	10	10	20	ME
Middlesex County Fetty Wap Fan Club	consumption smoothing by borrowing future big law income	0	10	10	E
Mike and Psmith	UNC Charity	10	10	20	ME
Muscle Mass Extinction Event	Northwestern	10	10	20	ME
NYU A	Untitled by Alexander McQueen by Premeditated Chaos by Alexander McQueen by Percival Everett	10	10	20	ME
No Country for Old Quizzers	C R A B S	0	10	10	E
Noah Sheidlower	NYU B or not NYU B (that is the question)	0	10	10	E
Penn State	JHU	0	10	10	E
Polish Orthographers Posting Their Łs	David Foster Gromit	10	10	20	ME
Rosslyn Academic Team	https://i.imgur.com/C6nN2FE.png	0	0	0
Say It Ain't Zhou	UTK	0	10	10	E
Shipping Down from Ballston	Negged Five Times in a Yellow Cab Against the Gottis and Gambinos	0	10	10	E
Stanford A	Constans Constantius and Constantine Jr.	10	10	20	ME
Stanford B	Not Old! (Old)	10	10	20	ME
Team 8	Berkeley B	0	10	10	E
The Saint-Straw that Broke the Camille's Back	Surrealist Subcommandante Marcos be like Esto no es una pipa	0	10	10	E
The Umayyad Caliphate be like REPEAL NAPHTHA	Girls who Just Want to Have Fun + Liam	0	10	10	E
UBC A	The Unbearable Heaviness of History Players	10	10	20	ME
UBC B	Abbas I founded the Abbasids	0	10	10	E
Untitled Keyal Team	Six Quizbowlers in Search of Owen Minmo	10	10	20	ME
Where's the nearest library, I need to have a public crashout.	Guelph Cloze	0	10	10	E
You Don't Have the Cards	Licence to C. Wright Mill	0	10	10	E

Summary

Tournament	Edition	Match	Heard	PPB	E %	M %	H %
2026 NAFTA at Stanford	01/17/2026	✓	4	17.50	100%	75%	0%
2026 NAFTA at UBC	01/17/2026	✓	2	15.00	100%	50%	0%
2026 NAFTA at Vanderbilt	02/14/2026	✓	3	13.33	100%	33%	0%
2025 NAFTA at Toronto	09/13/2025	✓	4	15.00	100%	50%	0%
2025 NAFTA at Maryland	09/27/2025	✓	4	12.50	75%	50%	0%
2025 NAFTA at Harvard	10/04/2025	✓	3	13.33	100%	33%	0%
2025 NAFTA at Oxford	10/11/2025	✓	4	12.50	100%	25%	0%
2025 NAFTA at Chicago	11/08/2025	✓	6	11.67	100%	17%	0%
2025 NAFTA at Columbia	11/08/2025	✓	5	16.00	100%	60%	0%
2025 NAFTA at Richmond	12/20/2025	✓	2	15.00	100%	50%	0%