floyd-warshall

这是一个Rust包，旨在高效地解决所有对最短路径问题（APSP）。它使用petgraph进行图存储，并使用Floyd-Warshall算法以O(V^3)的时间复杂度解决给定问题。

有关示例，请参阅测试用例。它包含两个简单的测试（一个完全连接的图和一个中间节点更短的图）以及一个随机图测试，以手动验证大型随机图的最短路径。

最终目标是使用Thorup (1999)的算法以O(VE)的时间复杂度解决相同的问题。

欢迎贡献力量！

待办事项列表

• 使用模拟
• 更多单元测试
• 更干净的API
• 更高效的路径保存
• 包含Thorup算法

许可证

本作品根据MIT许可证的条款授权。请参阅LICENSE。

lib.rs:

本包包含了一个弗洛伊德-沃舍尔算法的实现，用于解决无向图中的所有对最短路径问题。