الگوریتم Goldberg و Tarjan
مکاشفه ای > پیشگویی push

مکاشفه دیگر به نام پیشگویی push به گولدبرگ منتسب است. هدف آن اجتناب از هل دادن روند از یک راس  v به یک همسایه  \alpha . است اگر این روند در قدم بعد از آن احتمال دارد مجدداً به  v هول داده شود. ما الگوریتم را تغییر می‌دهیم و هل دادن را بیش از  A_{f}(w):=max\{0,-e_{f}(w)+\sum u_{f}(e)\} واحد از روند به راس  w انجام نمی‌دهیم. اگر این عدد مثبت باشد بیانگر تعداد روندهایی است که می‌تواند از  \alpha ، بدون relabeling هل داده شود.

لازم است رویه relabel را گسترش داد. اگر به اندازه  a_{f}(w)<min\{u_{f}(e),e_{f}(v)\} واحد از  v به
 w هل داده شود، راس  w به عنوان بیش فعال علامت می خورد. پس از آن هیچ روند اضافه‌ای نمی‌تواند به سمت  w هل داده شود تا این که  w، relabel  شود. به علاوه قبل از relabel  کردن
 v،  wرا نمی‌توان relabel کرد اما اگر  a_{f}(w)<0، آنگاه پس از آن که تمام هل‌های احتمالی از  w انجام گرفته باشد  w فعال نخواهد بود. این موضوع نشان می‌دهد که لازم است عمل relabel به رأس‌های بیش فعال گسترش داده شود. مستقل از این که آیا این رأس‌ها فعالند یا خیر.

گولدبرگ و خاریتونوف نیز پیشنهاد می‌دهند که رویه relabel به صورت فوق ذکر به رأس‌های پیش فعال اغمال شود با این فرق که در مواردی که هیچ یال باقی مانده‌ای راس relabel را ترک نمی‌کند، این احتمال به اندازه  \varepsilon  کاهش یابد. ما رویه relabel  متفاوت زیر را پیاده‌سازی کردیم.
{\text{procedure }}relabel(v)
 {\text{begin}}
   {\text{if }}f_{f}{v}=0{\text{ then}}
     {\text{Decrease }}\pi (v){\text{ by }}\varepsilon ;
   {\text{else}}
     {\text{replace }}\pi (v){\text{ by }}max_{(v,w)\in E(G_{f})}(\pi (w)-c(v,w)-\varepsilon );
 {\text{end;}}
دلیل ما برای انتخاب رویه relabel گسترش یافته آن است که نا را قادر می‌سازد که مقدار بیشینه قدر مطلق مقادیر بالقوه را محدود کنیم. این موضوع به دلایل عددی مهم است.

در هنگام بررسی یک راس بیش فعال  v امکان دارد راس دیگری مانند  w بیش فعال گردد. اگر رأس‌های بیش فعال در داخل یک پشته قرار دهیم و همیشه آخرین راس بیش فعال اضافه شده را در نظر داشته باشیم می‌توان این رأس‌ها را با ترتیب سریع بررسی کرد.( توجه شود که گراف قابل تصدیق فاقد چرخه است). رویه بازگشتی زیر این موضوع را منعکس می‌کند.
{\text{procedure }}refine(\varepsilon ,f,\pi )
 {\text{begin}}
   {\text{for }}e\in E({}_{f}^{\pi }G){\text{do push}}(e,u_{f}(e));
   {\text{while there exists an active vertex do}}
   {\text{begin}}
     {\text{choose an active vertex}}v
     discharge(v);
   {\text{end;}}
 {\text{end;}}
{\text{procedure }}discharge(e,\delta )
 {\text{begin}}
   {\text{while }}e_{f}(v)>0{\text{ or }}v{\text{ is hyperactive do}}
   {\text{begin}}
     {\text{if }}{}_{f}^{\pi }{\text{contains an edge }}e=(v,w){\text{then}}
     {\text{begin}}
       push(e,min(u_{f}(e),e_{f}(v),a_{f}(w)));
       {\text{if }}a_{f}(w)<min(u_{f}(e),e_{f}(v)){\text{ then}}
       {\text{begin}}
         {\text{mark }}w{\text{ as hyperactive}}
         discharge(w);
       {\text{end;}}
     {\text{end;}}
     {\text{else}}
     {\text{begin}}
       relabel(v);
       {\text{if }}v{\text{ is hyperactive then}}
       {\text{begin}}
         {\text{mark }}v{\text{ as non-hyperactive}}
         {\text{return;}}
       {\text{end;}}
     {\text{end;}}
   {\text{end;}}
 {\text{end;}}
تعداد عمل‌های relabel که به هر راس اعمال می‌شود را کماکان می‌توان به  (\alpha +1) محدود کرد. در عمل تعداد عمل‌های relabel تقریباً ثابت می‌ماند در حالی که تعداد عمل‌های push به اندازه 40-60% کاهش می یابد. به علاوه روند محاسبه شده توسط رویه refine جدید معمولاً بهتر است یعنی برای  \varepsilon ' کوچکتری  \varepsilon '-بهینه است. در نتیجه ترکیب با مکاشفه پالایش قیمت توصیف شده در فصل قبل بسیار کارآمد می‌باشد.