Rust Dijkstra CLI:最小堆实现
一个用 Rust 编写的 Dijkstra 最短路径 CLI 工具。核心实现要点:
- 逆转 State 的 Ord 将 BinaryHeap 最大堆当作最小堆使用,并反转次要键以确保等距时路径确定性(测试已验证)。
- 通过比较 dist 与 best[idx] 跳过过期堆条目(lazy deletion),无需 decrease-key,仍保持 O((V+E) log V)。
- 记录前驱节点重建路径;解析边时拒绝负权值并提示使用 Bellman-Ford。
GitHub: GitHub
作者主页:
#开发者 #工具 #Dijkstra #Rust #CLI #图算法 #最短路径
📢 频道:@DevToolboxHub
Post #1084
5

