最大流问题的Goldberg-Tarjan预流推进算法.pdf

15.082 和 6.855J 最大流问题的Goldberg-Tarjan 预流推 进算法 预流推进 4 2 5 3 1 1 1 2 4 s 4 t 3 2 1 3 这是初始网络加上弧的反向. 预流推进 4 2 5 3 1 1 1 2 4 s 4 t 3 2 1 3 这是初始网络和初始剩余网络. 初始化距离 4 2 51 5 3 1 1 1 4 3 2 4 s2 41 0t 2 2 s 3 2 1 1 3 4 5 31 0 t 结点标号从此以后将是距离标号. d(j) 是在G(x)中从j 到 t的最大距离. 饱和从结点s发出的弧 3 s 4 2 51 5 3 1 1 1 4 3 2 4 s26 41 0t 2 2 s 3 2 2 1 1 3 4 5 31 0 t 3 饱和从结点 s 发出的弧. 移动超额到关联的弧 当所有关联的弧都已经饱和，重标号结点s. 选择, 然后重标号/推进 3 s 4 2 51 5 3 1 1 1 4 3 2 4 s26 41 0t 2 2 s 3 2 2 1 1 3 4 5 31 0 t 31 选择活动结点, 也就是, 超额结点 推进/重标号 当推进之后更新超额 选择, 然后重标号/推进 3 s 4 2 51 5 3 1 1 1 4 3 2