Potential Performance Boost: Implementing the New Tsinghua SSSP Algorithm

[Yona-TYT]

(This was created with AI, but the news is real, https://iiis.tsinghua.edu.cn/en/info/1018/2438.htm)

Hi everyone,
I've been following a recent breakthrough in computer science that might be highly relevant for Simutrans performance, especially when dealing with extremely large maps.
A team from Tsinghua University recently published a paper that breaks a 41-year-old record in graph theory. For the first time since 1984, they have improved upon the complexity of Dijkstra's algorithm (using Fibonacci heaps) for the Single-Source Shortest Path (SSSP) problem in directed graphs with non-negative weights.

The Technical Part:
While the classic Dijkstra/Fibonacci heap implementation sits at \(O(m + n \log n)\), the new algorithm achieves a complexity of \(O(m \sqrt{\log n})\). It replaces traditional priority queues with a "Two-level Bucket Hierarchy."

Why this matters for Simutrans:
As hardware allows us to run increasingly massive maps (reaching tens of millions of tiles), pathfinding overhead for passengers, mail, and freight becomes a critical bottleneck.
On an extreme scale:

• The \(\log n\) factor in traditional Dijkstra starts to weigh heavily on CPU cycles during massive route recalculations.
• The new "Bucket Hierarchy" structure is designed to be more hardware-friendly regarding cache hits compared to the random memory access patterns of large heaps.

Discussion points:

• How deeply is the current Dijkstra/A* implementation tied to the core engine, and would it be feasible to swap the priority queue for a Two-level Bucket Hierarchy?
• Would the constant overhead of this new algorithm be too high for "standard" maps, or could it be implemented as an optimization for large-scale simulations?
• Has anyone looked into the paper yet regarding its potential implementation in C++?

References:

• Original Paper: "A Deterministic Algorithm for the Single-Source Shortest Path Problem" by Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, et al. (FOCS 2024).
• Technical Context: Quanta Magazine - Computer Scientists Break 40-Year-Old Dijkstra Record

I'd love to hear the devs' thoughts on whether this could eventually help mitigate performance drops in massive savegames.