Двухэтапная эвристика

Question

Я не понимаю, как реализовать эвристику гэпа с помощью push relbel. Вики описал это так:

"В эвристике перебрасывания промежутков мы поддерживаем массив A размером n, содержащий в A[i] количество узлов для каждой метки (до n). Если найдена метка d, такая, что A[d] = 0, то все узлы с меткой> d помечены меткой n."

Используйте эвристический разрыв. Если есть такое "k", что для высоты узла нет (u) =k, вы можете установить высоту (u) = max(высота (u), высота (источник) +1) для всех узлов, кроме источника, для которого высота (и) > к. Это связано с тем, что любое такое "k" представляет минимальный разрез в графе, и поток больше не пойдет от узлов S={u, где height(u) >k}, к узлам в T={v, где height(v)0. Но тогда высота (u) > высота (v)+1, противореча высота (u) >k и высота (v)

Может ли кто-нибудь объяснить мне в псевдокоде, как добавить эвристику гэпа в push-релевант FIFO, как показано в примере кода вики?

Спасибо Винс

Answer 1

Это может быть немного поздно, но здесь есть ссылка на блокнот Стэнфордского университета, где вы можете найти максимальный поток push-relbel, используя эвристику Gap в C. Надеюсь, она вам поможет.

http://www.stanford.edu/~liszt90/acm/notebook.html