I wrote a library for finding paths on arbitrary graphs, and I would like to share it with you .
An example of use on a huge graph:
To play around with the demo, you can here
The library uses a little-known version of the A * search, which is called NBA * . This is a bidirectional search, with relaxed requirements for the heuristic function, and a very aggressive termination criterion. Despite its little-known algorithm, the algorithm has an excellent speed of convergence to the optimal solution.
The description of the various variants of A * has already been found on the hub several times. I really liked this is , so I will not repeat this article. Under the cut I will explain in more detail why the library works quickly and how the demo was done.