pub fn par_dijkstra<T, E, F>(
graph: &Graph<T, E>,
source: NodeIndex,
get_weight: F,
delta: f64,
) -> GraphResult<HashMap<NodeIndex, f64>>Expand description
并行 Dijkstra 算法(delta-stepping 简化版)
§锁设计
此实现使用混合锁/无锁数据结构:
- 桶队列: 使用
crossbeam-queue::SegQueue无锁并发队列 - 距离数组: 使用
AtomicU64存储距离的位表示,支持无锁 CAS 更新 - 完成标记: 使用
AtomicBool标记已完成的节点
注意:虽然核心数据结构使用无锁操作,但桶队列的 pop() 操作内部存在细粒度锁。
在稠密图上,锁竞争可能带来一定开销。
使用桶式优先队列实现并行松弛操作 适用于非负权重的图,delta 参数控制桶的粒度
§参数
graph- 图source- 源节点get_weight- 获取边权重的闭包(需要是 Fn 而非 FnMut)delta- 桶宽度(默认 1.0)
§返回
HashMap,键为节点索引,值为最短距离
§复杂度
- 时间:O((V + E) * log(V) / P),P 为并行度
- 空间:O(V + E + B),B 为桶数量