Алгоритм максимального потока Голдберга-Рао - почему некоторые дуги никогда не допустимы?
Я пытаюсь реализовать алгоритм максимального потока Голдберга-Рао, описанный в статье " Вне барьера разложения потока, 1988". В статье говорится, что мы ищем поток на допустимых дугах.
The arc(vw) is admissible if distance(v) > distance(w) + length(vw).
Чтобы найти длину дуги, нам нужны следующие вычисления:
Initially, F = sum of capacities of all arc's leaving the source
lambda = min (num of nodes ^ 2/3 , num of arcs ^ 1/2)
Δ = F/lambda
length equals 0 on arcs with large residual capacities (res.cap >= 3Δ) and 1 otherwise
Во время алгоритма вычислений F можно только уменьшить. Таким образом, если есть дуги с большой емкостью, они никогда не станут допустимыми, и мы не сможем протолкнуть поток через них.
В примере F = 5, лямбда = 1,7, Δ = 3 - поэтому дуга от 2 до Т с пропускной способностью 10 недопустима.
кто-нибудь знает, как решить эту проблему? И как именно ограничение верхней границы дуги улучшает поиск максимального потока?