@macil/pathfinding

This library implements several pathfinding and graph algorithms. This library works with Typescript and Javascript in both Deno and Node.

Where possible, this library does not need an entire graph to be provided to it ahead of time. Many functions allow nodes and edges to be provided by a successor function executed for each node encountered, meaning that graphs are lazily initialized which allows for procedural and infinite graphs to be used.

Algorithms

Directed graphs

• A*: find the shortest path in a weighted graph using an heuristic to guide the process.
• Dijkstra: find the shortest path in a weighted graph.

Undirected graphs

• connected components: find disjoint connected sets of vertices.

Related Projects

This project was ported from the Rust pathfinding library.

License

This code is released under a dual Apache 2.0 / MIT free software license.

Contributing

You are welcome to contribute by opening issues or submitting pull requests.

Implementations of additional similar graph algorithms, especially those in the Rust pathfinding library, are welcome.