Skip to main content

dinic

god_graph::algorithms::flow

Function dinic 

Source 
pub fn dinic<T, E, F>(
    graph: &mut Graph<T, E>,
    source: NodeIndex,
    sink: NodeIndex,
    capacity: F,
) -> f64
where
    F: FnMut(NodeIndex, NodeIndex, &E) -> f64,
Expand description

Dinic 最大流算法

使用分层图和阻塞流的高效最大流算法

§内存优化

使用 HashMap<usize, HashMap<usize, f64>> 存储残量，空间复杂度 O(V+E) 对于稀疏图（E << V²），比邻接矩阵 O(V²) 节省 10-100x 内存

§复杂度

  • 时间：O(V² * E)
  • 空间：O(V + E)