Implementing FRE in Production: Breaking the Sorting Barrier
Implemented FRE algorithm from Duan et al.'s 2025 paper in production Zig. Achieved O(m log^(2/3) n) complexity for single-source shortest paths, improving on Dijkstra's O(m + n log n). Shows advantage on large sparse graphs by breaking the sorting barrier, but overhead kills performance on small or dense graphs.