Cool! Another (more modest) improvement is Uniform Cost Search[1] (see comparison with DA: https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4

Cool! Another (more modest) improvement is Uniform Cost Search[1] (see comparison with DA: https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357 https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFil... ) which then leads naturally to A* and bidirectional search which can be augmented with pre-processing. (Good summary: https://www.microsoft.com/en-us/research/publication/point-to-point-shortest-path-algorithms-with-preprocessing/ https://www.microsoft.com/en-us/research/publication/point-t... ) [1] Despite what wikipedia says, UCS is not the same as DA.