An Implementation and Audit of the Duan–Mao–Shu–Yin Directed Shortest-Path Algorithm

This note reports the first implementation, as far as we are aware, of the O(m√(log n · log log n)) directed single-source shortest-path algorithm of Duan, Mao, Shu and Yin (arXiv:2602.07868), in Rust, verified bit-for-bit against a pure-Python reference audited line by line against the paper. Measured: the algorithm is not faster than Dijkstra at any storable input size. The faithful port trails an optimized Dijkstra by 38–182x; an engineered family of variants closes to 1.8–2.2x and ends as lazy Dijkstra carrying the paper's 16-byte labels. The prescribed degree parameter falls outside the paper's own validity range on every input below n = 2^4096. Audited: two lines of the printed pseudocode crash on ordinary graphs, and Lemma 3.7 fails twice — its bound clause is violated at scale on unit positive weights, and its completeness clause is false as stated: on a 70-vertex graph the algorithm settles a vertex whose distance is not yet final, and a variant that trusts the clause returns a wrong distance. A one-line repair closes the hole, and the note includes a hand proof (not machine-checked) that on the repaired engine every settlement carries the lexicographically minimal (length, hop count) label, bit-final.