Research · Research prototype
LPQ Atlas
Can a learned priority queue speed up Dijkstra without breaking correctness?
In plain words. An experiment in making route-finding (like a map app picking the shortest way) faster with machine learning, while making sure the answer is still always correct. It includes a visual tool that replays how each search worked.
The problem
Shortest-path search is dominated by priority-queue behaviour, and a model that orders candidates cheaply must still return correct distances once inference and verification costs are counted.
What it does
A C++ engine and interactive web interface for running Dijkstra or A* with classical or learned queues, inspecting execution traces and comparing configurations. The UI replays machine-readable output from the real engine, not an animation.
Key decisions
- Learned suggestions are verified or bypassed by deterministic logic, so exact mode keeps classical guarantees.
- A separate untraced run is the authoritative timing; a traced run exists for visualisation and is checked against it.
- Model setup, scoring, verification and fallback are counted separately so a headline speedup can be interpreted.
Limits and status
- Learned priority queues are published prior work; no novelty claim is made.
- Speedups need reproduction on stated hardware, and a faster classical queue is not evidence that ML helped.