# floyd-warshall

This is a rust crate which aims to solve the all-pairs-shortest-paths (APSP) problem efficiently. It uses [petgraph](https://crates.io/crates/petgraph) for graph storage and the Floyd-Warshall algorithm to solve the given problem in **O(V^(3))** runtime.

For examples, please have a look at the test cases. It consists of two simple tests (one fully connected graph and one graph, where it's shorter to use an intermediate node) and a random graph test, to manually verify the shortest paths for larger, random graphs.

The ultimate goal is to use the algorithm by [Thorup (1999)](https://dl.acm.org/citation.cfm?id=316548) to solve the same problem in **O(VE)** runtime.

Contributions are welcome!

## TODO-List

- Use mocking
- More unit tests
- cleaner API
- more efficient path saving
- include [algorithm by Thorup](https://dl.acm.org/citation.cfm?id=316548)

# License

This work is licensed under terms of the MIT License. See LICENSE.