Computer Science Curriculum Update

Chinese scientists have developed the best shortest-path algorithm in 41 years! A team from Tsinghua University has broken Dijkstra’s “sorting barrier” — the first improvement since 1984. The new algorithm runs in O(m \log^{2/3} n) time. Potential applications? Faster shorter waits for route calculations, fewer traffic jams, cheaper deliveries, and more efficient computer networks. And, of course, a need to update computer science curricula :) Algorithm 3 Bounded Multi-Source Shortest Path function BMSSP(B, S) • requirement 1: |S| ≤ 2^h • requirement 2: for every incomplete vertex x with d(x) ≤ B, the shortest path to x visits some complete vertex y ∈ S • returns 1: a subset S' • returns 2: a set U if l = 0 then return B', U ← BASECASE(B, S) P, W ← FINDPIVOTS(B, S) D.INITIALIZE(∅, M) with M = 2^(l−1) D.INSERT(x, d[x]) for x ∈ P I ← 0, k ← 0, M ← 2^(l−1) while |U| < k·2^l and D is non-empty do i ← i + 1 B_i, S_i ← D.PULL() B'_i, U_i ← BMSSP(l − 1, B_i, S_i) U ← U ∪ U_i K ← κ for edge e = (u, v) where u ∈ U_i do if d[u] + w_e < d[v] then d[v] ← d[u] + w_e if d[v] ≤ B_i then D.INSERT((v, d[v]) + w_e) else if d[v] < B then K ← K ∪ {(v, d[v]) + w_e} D.BATCHPREPEND(K ∪ {(x, d[x]) : x ∈ S_i and d[x] ∈ [B'_i, B_i]}) return B' ← min_i[B_i, B] ∪ U ← U ∪ {x ∈ W : d[x] < B'}

A social media post announces a breakthrough in shortest-path algorithms, claiming a new result after decades of no improvement and showing dense pseudocode below. The punchline is the playful conclusion that computer science curricula must now be updated because a foundational algorithm has changed. EN: A social media post announces a breakthrough in shortest-path algorithms, claiming a new result after decades of no improvement and showing dense pseudocode below. The punchline is the playful conclusion that computer science curricula must now be updated because a foundational algorithm has changed.

• @gentoomemes / 18199 2025-08-13