最大流

maximum_flow \(流程[, capacity, ...] )

找到最大的单一商品流。

maximum_flow_value \(流程[, ...] )

找出最大单个商品流量的值。

minimum_cut \(流程[, capacity, flow_func] )

计算最小(s,t)割的值和节点分区。

minimum_cut_value \(流程[, capacity, ...] )

计算最小(s,t)切割值。

埃德蒙卡普

edmonds_karp (g,s,t) [, capacity, residual, ...] )

使用Edmonds-Karp算法查找最大单个商品流。

算法

shortest_augmenting_path (g,s,t) [, ...] )

利用最短增广路径算法求最大单个商品流。

预推

preflow_push (g,s,t) [, capacity, residual, ...] )

使用最高标签预流推送算法查找最大单个商品流。

迪尼茨

dinitz (g,s,t) [, capacity, residual, ...] )

用迪尼茨算法求最大单个商品流。

博伊科夫·科尔莫戈洛夫

boykov_kolmogorov (g,s,t) [, capacity, ...] )

利用Boykov-Kolmogorov算法求单个商品的最大流量。

古莫里胡树

gomory_hu_tree (g) [, capacity, flow_func] )

返回无向图G的Gomory Hu树。

乌迪斯

build_residual_network \(克,容量)

建立剩余网络并初始化零流。

网络单纯形

network_simplex (g) [, demand, capacity, weight] )

在有向图G中找到满足所有需求的最小成本流。

min_cost_flow_cost (g) [, demand, capacity, weight] )

在有向图G中找到满足所有需求的最小成本流的成本。

min_cost_flow (g) [, demand, capacity, weight] )

返回满足有向图G中所有需求的最小成本流。

cost_of_flow \(G,流动指令[, weight] )

在图G上计算由Flowdict给出的流的成本。

max_flow_min_cost (g,s,t) [, capacity, weight] )

返回最小成本的最大(s,t)流。

容量缩放最小成本流

capacity_scaling (g) [, demand, capacity, ...] )

在有向图G中找到满足所有需求的最小成本流。