3 ms·

For those who are searching for improved Dijkstra's algorithm, delta-stepping is a good one: https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/delta-stepp

• cgearhart 10y ago
  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.