Skip to main content

par_dijkstra

Function par_dijkstra 

Source
pub fn par_dijkstra<T, E, F>(
    graph: &Graph<T, E>,
    source: NodeIndex,
    get_weight: F,
    delta: f64,
) -> GraphResult<HashMap<NodeIndex, f64>>
where T: Clone + Send + Sync, E: Clone + Send + Sync, F: Fn(NodeIndex, NodeIndex, &E) -> f64 + Send + Sync,
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 为桶数量