floyd-warshall
| Crates.io | floyd-warshall |
| lib.rs | floyd-warshall |
| version | 0.0.3 |
| source | src |
| created_at | 2017-10-25 21:21:11.791949 |
| updated_at | 2017-11-02 18:48:11.017801 |
| description | Efficient all-pairs-shortest-paths algorithm for the petgraph library using the floyd-warshall algorithm. |
| homepage | |
| repository | https://github.com/zombiemuffin/floyd-warshall/ |
| max_upload_size | |
| id | 36930 |
| size | 18,209 |
(zombiemuffin)
documentation
https://docs.rs/floyd-warshall
README
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.