floyd-warshall

This is a rust crate which aims to solve the all-pairs-shortest-paths (APSP) problem efficiently. It uses 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) 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

License

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

lib.rs:

This crate contains an implementation of the Floyd-Warshall algorithm to solve the all-pairs-shortest-paths problem in undirected graphs.