الگوریتم Goldberg و Tarjan

فرض می‌کنیم با تئوری روند شبکه آشنایی داریم و نتایج و نشان‌گذاری استاندارد را استفاده می‌کنیم.
برای مثال آهوجا(Ahuja)، مگنانتی(Magnanti)،ارلین(Orlin)را  ببینید. در اینجا فقط مهمترین‌ها را ذکر می‌کنیم. مسئله روند کمترین هزینه به این صورت تعریف می‌شود: گراف جهت دار G با گنجایش u داده شده‌است: E(G)\rightarrow R_+ ، سنگینی c:E(G)\rightarrow R  و ارزش تعادل b:V(G)\rightarrow R، b را به عنوان یک روند کمترین روند هزینه بیابید، به‌طوری‌که تابع f:E(G)\rightarrow R_+ با F(e) \le u(e) برای همهٔ e‌های عضو E(G) و \sum_{e \in \delta_G^+(v)}f(e)-\sum_{e \in \delta_G^-(v)}برای همهٔ v‌های عضو V(G) از قبیل \sum{e \in E(G)}(f(e)c(e)) که کمترین مقدار یا همان مینیموم می‌باشد \delta_G^+مجموعه‌ای از ورودی‌های را تشکیل می‌دهد. راس v باقی می‌ماند.
واضح است که امکان وجود روند کمترین هزینهٔ مسائل، می‌تواند در برابر محاسبه روند ماکسیموم چک شود ( و در بهترین شرایط روند b می‌تواند پیدا شود). مسائل روند ماکسیموم آسانترند و خیلی سریعتر از مسائل روند کمترین  هزینه حل می‌شوند.
نمونه داده شده (G,u,c,b) از مسئله روند کمترین هزینه و روند
f:E(G)\rightarrow R_+ با f(e) \le u(e) برای همهٔ e \in E(G)، ظرفیت باقی‌ماندهٔ یال e \in E(G) به وسیله u_f(e) := u(f)-f(e) تعریف می‌شود.
علاوه بر این، ما یک یال جدید  e از w به v  برای هر یال
e = (v,w) در نظر گرفته ایم و u_f(e) := f(e) و
c(e) := -c(e) تعریف کرده ایم. باقی‌مانده گراف G_f شامل همه بال‌ها ( قدیمی و جدید) با ظرفیت باقی‌مانده مثبت می‌باشد. معروف است که روند b از f بهینه است( کمترین هزینه را دارد) اگر و تنها اگر هیچ جریان مستقیم در G_f وزن منفی نداشته باشد.
دیاگراف G داده شده با وزن c:E(G)\rightarrow R، یک ذخیره امکانپذیر در (G,c) است، تابع \pi:V(G)\rightarrow R به این صورت که هزینه کاهش یافته C\pi(e) := c(e)+\pi(v)\pi(w) است  که برای هر e نامنفی عبارت e= (v,w) برقرار است. یک ذخیره امکانپذیر وجود دارد اگر و تنها اگر هیچ جریان مستقیمی، وزن کل منفی نداشته باشد. این توسط کوتاه‌ترین راه محاسبه منبع واحد قطعی و تصمیم گرفته می‌شود.
روند داده شدهf:E(G) \rightarrow R_+ با f(e) \le u(e) و ذخیره
\pi:V(G) \rightarrow R، یک گراف مجاز تعریف می‌کنیم که تمام یال‌های G_f که هزینهٔ کاهش یافته منفی را دارند، در بر بگیرد. گراف مجاز را با {}_f^\pi G معنی می‌کنیم. اگر f یک روند b بهینه باشد( برای بعضی از bها) و
\pi یک ذخیره امکانپذیر در G_f باشد، پس   مارپیچ است.

## 1- مسئله گردش با کمترین هزینه
ورودی‌های مسئله عبارتند از:
* گراف جهت دار G=(V, A)
* هزینه‌ها که اعداد صحیح هستند. c_{ij} \in Z,\forall(i,j) \in A
* ظرفیت‌ها که اعداد صحیح هستند. u_{ij} \ge 0,\forall(i,j) \in A
* تقاضاها که اعداد صحیح هستند. 0 \le l_{ij} \le u_{ij},\forall(i,j) \in A
هدف: یافته جریان f : A \rightarrow R^{\ge 0} است که\sum_{(i, j) \in A} c_{ij} f_{ij}
را مینیمم می‌کند به‌طوری که:
l_{ij} \le u_{ij}\quad \forall(i, j) \in A

\sum_{k:(i, k)\in A}f_{ik}-\sum_{k:(k, i)\in A}f_{ki}=0
تعریف 1:  یک گردش f شرایط زیر را ارضا می‌کند.
* f_{ij} \le u_{ij} \quad \forall(i, j) \in A
* f_{ij}=-f_{ji} \quad \forall(i, j) \in A
* \sum_{k:(k, i) \in A}f_{ki}=0
در این تعریف جدید، جریان در قوس اولیه f_{ij} شرط f_{ij} \le u_{ij} را ارضا می‌کند و هر واحد جریان هزینه c_{ij} را تحمیل می‌کند. جریان در قوس معکوس f_{ji} شرط f_{ji} \le u_{ji}= -f_{ij} را ارضا کرده و هزینه c_{ji}= -c_{ij} را برای هر واحد جریان تحمیل می‌کند. هزینه کل برای دو یال با جریان
f برابر c_{ij} f_{ij}+ c_{ji} f_{ji}=2c_{ij} f_{ij} است. بنابراین بهینه‌سازی هزینه کل برای این گراف جدید معادل بهینه‌سازی هزینه کل برای گراف اولیه است.
برای یک جریان f در گراف G گراف باقی‌مانده G_f=(V,A_f) را گرافی تعریف می‌کنیم که مجموعه یال‌های آن عبارتند از:
A_f=\left\lbrace(i, j) \in A : f_{ij}
کران بالای u_{ij}^f= u_{ij}- f_{ij} را برای یال (i, j) \in A_f تعریف می‌کنیم. واضح است که
\forall(i, j) \in A_f: u_{ij}^f 
تعریف 2: یک پتانسیل تابعی است به صورت p:V \rightarrow R
تعریف 3: فرض کنید تابع پتانسیل p داده شده‌است. هزینه کاهش یافته را به صورت زیر تعریف می‌کنیم:
c_{ij}^p= c_{ij}+ p_i-p_j
آنگاه داریم:
c_{ji}^p= c_{ji}+ p_j-p_i=-(c_{ij}+ p_i-p_j )= -c_{ij}^p
تعریف 4: هزینه یک دور \Gamma برابر است با:
c(\Gamma)=\sum_{(i,j) \in \Gamma}c_{ij}
تئوری 1: موارد زیر با هم معادلند.
* f یک گردش با کمترین هزینه است.
* هیچ دور با هزینه منفی در G_f وجود ندارد.
* تابع پتانسیل f موجود است که برای هر (i,j) \in A_f داریم c_{ij}^p \ge 0
## 2- الگوریتم حذف یک دور
تئوری فوق منجر به الگوریتمی برای محاسبه گردش با کمترین هزینه می‌شود. این الگوریتم به صورت زیر است.

فرض کنید که f یک گردش شدنی باشد.تا وقتی که A_f شامل دور منفی \Gamma است.
\Gamma را حذف کرده و  f را به روز رسانی کن.صحت الگوریتم فوق از تئوری بالا نتیجه می‌شود. اگر هزینه‌ها و ظرفیت‌ها، هر دو صحیح باشند، جریان بهینه f موجود است به نحوی که f_{ij} برای هر (i, j) \in A صحیح است. فرض کنید:
U=max \quad u_{ij_{(i, j) \in A}}

C=max \quad |c_{ij}|_{(i, j) \in A}
بنابراین هر گردش شدنی دارای هزینه حداکثری mCU و هزینه حداقلی -mCU است. چون حذف یک دور، هزینه گردش را حداقل به اندازه یک واحد کاهش می‌دهد، برای یافتن یک گردش بهینه به حداکثر O(mCU) حذف نیاز است.
برای رسیدن به این نتیجه‌گیری که الگوریتم فوق شبه چندجمله‌ای است، به دو مورد زیر نیاز داریم.
* یک گردش اولیه. (این گردش را می‌توان با محاسبه گردش ماکسیمم به دست آورد.)
* امکان چک کردن وجود دور با هزینه منفی. (این کار را می‌توان با استفاده از الگوریتم bellman-ford در زمان O(mn) انجام داد. بنابراین ما یک الگوریتم چندجمله‌ای داریم که در زمان O(m^2 nCU) اجرا می‌شود.
## 3- حذف دور با کمترین هزینه متوسط
با انتخاب مناسب دوری که در هر مرحله تکرار الگوریتم باید حذف شود، می‌توان یک الگوریتم با زمان چندجمله‌ای به دست آورد.
تعریف 5: فرض کنید که هزینه متوسط دور \Gamma برابر با \frac{c(\Gamma)} باشد که
c(\Gamma) هزینه دور و |\Gamma| تعداد یال‌های موجود در \Gamma است.
تعریف 6: فرض کنید گردش f  داده شده باشد و \mu(f) هزینه دور با کمترین هزینه متوسط باشد.
\mu(f)=min  \frac{c(\Gamma)}_{cycles \Gamma \subseteq A_f}
می توان با حذف دور با کمترین هزینه مینیمم، یک الگوریتم چندجمله‌ای به دست آورد. اکنون می‌توانیم الگوریتم زیر را بیان کنیم.

فرض کنید f یک گردش باشد
تا زمانی که \mu(f)
دور \Gamma با کمترین هزینه متوسط را حذف کن. f را به روز رسانی کنشرط \mu(f) معادل داشتن یک دور با هزینه منفی در A_f است. برای داشتن یک الگوریتم با زمان چندجمله‌ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله‌ای پیدا کنیم.
برای تحلیل الگوریتم فوق، تعدادی اصطلاح را تعریف می‌کنیم.
تعریف7: یک گردش f، \varepsilon-بهینه است اگر تابع پتانسیل p موجود باشد که برای هر  (i, j) \in A_f داشته باشیم c_{ij}^p \ge -\varepsilon
واضح است که f، 0-بهینه است؛ اگر و تنها اگر f یک گردش با کمترین هزینه باشد. برای هر گردش،
f، C-بهینه است. زیرا اگر برای هر i \in V قرار دهیم p_i=0؛ برای هر
(i, j) \in A_f داریم c_{ij}^p \ge -C.
تعریف 8: \varepsilon(f) کمترین \varepsilon است که f، \varepsilon- بهینه باشد.
دو مقدار \varepsilon(f) و \mu(f) به شکل جالبی به هم مرتبطند.
تئوری 2: برای یک گردش f داریم: \mu(f)=-\varepsilon(f)
اثبات: ابتدا نشان می‌دهیم \mu(f) \ge -\varepsilon(f).
چون
\exists p : c_{ij}^p \ge -\varepsilon(f)  \forall(i, j) \in A_f
با جمع کردن روی تمام یال‌های هر دور \Gamma می‌بینیم که

c^p (\Gamma) \ge \varepsilon(f)|\Gamma|. بنابراین برای دور با هزینه متوسط کمینه \Gamma داریم:

\mu(f)=\frac{c\left(\Gamma\right)}=\frac{c^p \left(\Gamma\right)} \ge -\varepsilon(f)
حال نشان می‌دهیم که \mu(f) \le -\varepsilon(f).
قرار می‌دهیم \bar c_{ij}=c_{ij}-\mu(f). آنگاه برای هر دور\Gamma در A_f داریم:
\bar c(\Gamma)=c(\Gamma)-|\Gamma|\mu(f) \ge c(\Gamma)-|\Gamma|  \frac{c(\Gamma)} = 0
راس s را به گراف اضافه کرده و و آن را به همه رئوس i، با یال‌هایی به وزن c_{si}=0 وصل می‌کنیم. پتانسیل p_i را برای گره i به صورت طول کوتاه‌ترین مسیر از s به i با استفاده از هزینه‌های \bar c_{ij} تعریف می‌کنیم. با استفاده از تعریف کوتاهترین مسیر داریم:
\forall(i, j) \in A_f, p_j \le p_i+\bar c_{ij}=p_i+c_{ij}-\mu(f)
که نتیجه می‌دهد:
\forall(i, j) \in A_f, c_{ij}^p=c_{ij}+p_i-p_j \ge \mu(f)
این بدان معنی است که f، -\mu(f)- بهینه است. بنابراین \varepsilon(f) \le -\mu(f)
فرض کنید گردش f داده شده باشد و f^{(k)} گردش به دست آمده بعد از k بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی f باشد. تئوری زیر ثابت می‌کند که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای اجرا می‌شود.
تئوری3: \varepsilon\left(f^{(1)}\right) \ge \varepsilon(f)
تئوری4: \varepsilon\left(f^{(m)}\right) \ge \left(1-\frac{1}{n}\right)\varepsilon(f)
که m و n تعداد یال‌ها و گره‌ها در گراف هستند.
تئوری5: اگر \varepsilon(f) \ge \frac{1}{n} گردش f بهینه است.
اثبات: این حقیقت که \varepsilon(f) \le \frac{1}{n} نشان می‌دهد که پتانسیل p موجود است که
\forall(i, j) \in A_f : c_{ij}^p>\frac{-1}{n}. بنابراین برای هر دور \Gamma \in A_f, c(\Gamma)=c^p>-1. با توجه به صحیح بودن هزینه‌ها داریم؛ c(\Gamma) \ge 0
حال با توجه به سه نتیجه قبل ثابت می‌کنیم که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای بر حسب اندازه ورودی، خاتمه می یابد.
تئوری6: الگوریتم حذف دور با کمترین هزینه متوسط Goldberg-Tarjan، به حداکثر O(mn\log(nC) ) تکرار نیاز دارد.
اثبات: هر گردش اولیه C- بهینه است. بعد از mn\log(nC) تکرار، با توجه به اینکه
\left(1-\frac{1}{n}\right)^n، داریم:
\varepsilon\left(f^{(k)}\right) \le \left(1-\frac{1}{n}\right)^{n\log(nC)}
اگر محاسبه دور با هزینه متوسط کمینه، زمانی برابر O(mn) داشته باشد، زمان اجرای الگوریتم Goldberg-tarjan برابر
O\left(m^2n^2\log(nC)\right) خواهد بود. البته توجه داشته باشید که این الگوریتم کاملاً چندجمله‌ای نیست.
اثبات تئوری 3: می‌دانیم پتانسیل p موجود است که:
\forall(i, j) \in A_f: c_{ij}^p \ge -\varepsilon(f)
به علاوه، \mu(f)=-\varepsilon(f). برای دور \Gamma با کمترین هزینه متوسط، چون
\mu(f)=\frac{c^p (\Gamma)}، نتیجه می‌گیریم که
\forall(i, j)\in \Gamma, c_{ij}^p \ge -\varepsilon(f). حال ادعا می‌کنیم که
\forall(i, j) \in A_{f^{(1)}}:c_{ij}^p \ge -\varepsilon(f). داریم (i, j)\in A_{f^{(1)}}، اگر
 (i, j) \in A_f یا (j, i) \in \Gamma. در حالت اول، c_{ij}^p \ge -\varepsilon(f). در حالت دوم، c_{ij}^p=c_{ji}^p=\varepsilon(f) \ge 0. در هر دو حالت، f^{(1)}،
\varepsilon(f) -بهینه است و تئوری ثابت می‌شود.
اثبات تئوری4: می‌دانیم پتانسیل p موجود است که
\forall(i, j) \in A_f: c_{ij}^p \ge -\varepsilon(f). فرض کنید در تکرار k، دور \Gamma را حذف می‌کنیم که در آن،
\exists (i, j) \in \Gamma : c_{ij}^p \ge 0. آنگاه
\varepsilon\left(f^{(k)}\right)=\mu\left(f^{(k)}\right)=\frac{c^p(\Gamma)}\ge\frac{|\Gamma|-1}\left(-\varepsilon(f)\right)\ge\left(1-\frac{1}{n}\right)(-\varepsilon(f))
بنابراین
\varepsilon\left(f^{(k)}\right)\le\left(1-\frac{1}{n}\right)(\varepsilon(f))

حذف دور، یک یال با c_{ij}^p را از گراف باقی‌مانده حذف و تنها یال‌هایی با c_{ij}^p>0 را ایجاد می‌کند. بنابراین برای حذف چنین یالی به بیش از m تکرار نیاز نیست.
انتزاعی
الگوریتم هزینه پیمایش گولد برگ (Goldberg) و تارجان(Tarjan)، یکی از کارآمدترین الگوریتم‌ها، برای روند کمترین هزینهٔ مسائل، شناخته شده‌است. اگر چه بازده آن در عمل، به بسیاری از جوانب اجرا بستگی دارد. علاوه بر این، گنجایش بسیاری از ابتکارات، کارایی آن را شدیدا بهبود می‌بخشد. در این مقاله به شرح جوانب اجرا و کارآمدترین ابتکارات، می پردازیم. همچنین، نتایج تجربی، اثر ابتکارات مختلف ترکیبی را پررنگ می‌کند.

## الگوریتم گولبرگ و تارجان
یک روند b، \varepsilon -بهینه نامیده می‌شود اگر یک ذخیره \pi:V(G)\rightarrow R مانند c_{\pi}(e) \ge -\varepsilon برای همهٔ  e \in (G_f). پس بهینه 0 هیچ چیز نیست ولی بهینه است. الگوریتم هزینه پیمایش گولبرگ و تارجان  یک روند b را محاسبه می‌کند که بهینه \varepsilon برای بعضی از \varepsilon‌های بزرگ است. پس مقدار \varepsilon را در هر تکرار، نگهداری کردن و بهینگی \varepsilon، کاهش می‌دهد.
ساده است که هر روند b، بهینه \varepsilon است اگر
\varepsilon \ge max_{e \in E(G)}\quad |c(e)| . علاوه بر این، از دید هزینه‌های  انتگرال، هر روند \varepsilon-بهینه با \varepsilon ، بهینه است.

پس ساختار جهانی این الگوریتم، به صورت زیر است.
(\alpha یک پارامتر ثابت است و حداقل مقدار آن 2 می‌باشد)

 \text{procedure }minimum\_cost\_flow(G, u, c, b)
 \text{begin}
   \pi (v) := 0 \quad \forall v \in V(G) \text{ and } \varepsilon:= max_{e\in E(G)} |c(e)|;
   \text{Determine a b}\_\text{flow f. If no b}\_\text{flow exists, return(null);}
   \text{while }\varepsilon \ge \frac{1}{n} \text{ do }
     \varepsilon :=\frac{\varepsilon}{\alpha}
     \text{refine}(\varepsilon , f,\pi)
   \text{end;}
   \text{return}(f);
 \text{end;}

این روال دستوری( مجموعه کد) به صورت زیر اجرا می‌شود:
ابتدا مقدار ممکن ماکسیموم از رونددر طول همهٔ یال‌ها با هزینه کاهش یافته منفی هل داده می‌شود. این نتیجه یک روند b' بهینه برای بعضی b'‌ها است. یک راس فعال نامیده می‌شود اگر اضافی باشد.
e_f(v):=b(v)-\sum_{e \in {}_G^+\delta (v)}f(e)+\sum_{e \in {}_G^-\delta (v)}f(e)
تا زمانی که حتی یک راس فعال وجود داشته باشد، چه relabel یا چه push، به جای راس فعال اجرا می‌شود.

 \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
     \text{if }{}_f^\pi G \text{ contains an edge }e=(v, w)\text{ then}
       \text{push}(e, min(u_f(e), e_f(v)));
     \text{else}
       \text{relabel(v)}
     \text{end;}
  \text{end;}

 \text{procedure push}(e, \delta)
 \text{begin}
   \text{if }e=(v,w)\in E(G)\text{ then}
     \text{increase }f=(e)\text{ by }\delta;
   \text{else}
     \text{decrease }f(\leftarrow e) \text{ by }\delta;
 \text{end;}

 \text{procedure }relabel(v)
 \text{begin}
   \text{replace }\pi(v) \text{ by }max_{(v,w)\in E(G_f)}(\pi(w)-c(v,w)-\varepsilon);
  \text{end;}

هر اجرای refine، O(n^2) عمل relabel و O(n^2m). عمل push استفاده می‌کند که n:= |V(G)| و m := |E(G)|. اثبات این موارد قبلاً ذکر شده‌است.

 ملاحظه می‌کنیم که به‌طور تئوری زمان refine را می‌توان با استفاده از درخت‌های پویا به O\left(nm\log(\frac{n^2}{m})\right) بهبود داد.
برای محاسبه روند b اولیه، الگوریتم روند ماکسیموم گولدبرگ و تارجان استفاده می‌شود. در آزمایش‌های ما فقط بخش کوچکی از زمان اجرا برای این قدم اولیه مصرف شد.
## جنبه‌های پیاده سازی
تصمیم اولیه در هنگام پیاده‌سازی الگوریتم فوق مربوط به گراف باقی مانده‌ای است: لازم نیست که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم. اما اگر بدون ذخیره‌سازی عمل شود، لازم است تمام یال‌های همسایهٔ یک راس فعال چک شود قبل از این که بتوان آن را relabel کرد. این کار بسیار پر هزینه است. لذا تصمیم گرفتیم که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم به وجودی که لازم است بعد از هر عمل push آن را به روز کنیم.
ظرفیت باقی مانده‌ای ذخیره و در هر یال به روز می‌شود. در نتیجه نیازی به ذخیره روند نیست. در حقیقت روند به‌طور صریح مورد نیاز نیست مگر در زمان باز گرداندن خروجی بعد از پایان الگوریتم. برای هر راس v،افزونگی e_f(v) و
\pi(v) احتمالی  ذخیره می‌شود. هزینه‌های کاهش یافته به‌طور صریح ذخیره نمی‌شوند چون مشخص گردید که به صرفه تر است که هر گاه که مورد نیاز بودند مجدداً محاسبه شوند. برای هر راس لیستی از یال‌های خارج شونده با ظرفیت باقی مانده‌ای مثبت موجود است. اشاره‌گری داریم که برای هر راس فعال عنصر جاری در این لیست را نشانه‌گذاری می‌کند. هرگاه یک push یال جاری را اشباح کند( یا وقتی که الگوریتم مشخص می‌کند که یال جاری دارای هزینه کاهش یافته غیر منفی است) اشاره گر به جلو حرکت می‌کند. این امر متضمن آن است که یک relabel می‌تواند زمانی که اشاره گر به انتهای لیست می‌رسد انجام پذیرد.
یک امر مهم در پیاده‌سازی انتخاب راس فعال است. با توجه به این که تعداد رأس‌های فعال معمولاً کم است لازم است که ساختمان داده‌ای استفاده شود که مجموعه گره‌های فعال را در بر دارد. ساختمان داده‌های ساده یا یک صف یا یک پشته هستند. راه پیچیده تر عبارت است از ذخیره کردن رأس‌های فعال به صورت یک ترتیب مبتنی بر همبندی نسبت به گراف قابل تصدیق ( که غیر چرخه‌ای است). اما در عمل تعداد عملیات pushو relabel اندکی بزرگتر از حالتی است که از پیاده‌سازی ساده صف استفاده می‌شود. به علاوه انتخاب اولین راس با ترتیب مبتنی بر همبندی پر هزینه تر است حتی موقعی که از کارآمدترین ساختمان داده، دنباله فیبوناچی استفاده شود. با توجه به این ملاحظات تصمیم گرفتیم که رأس‌های فعال را در یک صف ساده ذخیره کنیم. توجه شود که این رویکرد مرز تئوری بر روی تعداد عملیات push را برای هر بار اجرای refine به O(n^3) کاهش می‌دهد.
## مکاشفه ای
### پالایش قیمت
رویه refine یک روند b ،\varepsilon-بهینه محاسبه می‌کند. از طرفی بسیار اتفاق میافتد که این روند از قبل برای بعضی از \varepsilon' بهینه برای بعضی از \varepsilon' . در این صورت ممکن است بتوانیم از بعضی تکرارها بدون اجرای refine صرف نظر کنیم در نتیجه دو سؤال مطرح می‌شود
#برای بک روند b به نام f یک \varepsilon \ge 0 یک \pi V(G) \rightarrow R بالقوه پیدا می‌کنیم مانند c_\pi(e) \ge =\varepsilon برای همه e \in E(G_f) یا یک f که \varepsilon بهینه نباشد، تعریف می‌شود.
#برای یک روند b به نام f، کوچکترین \varepsilon \ge 0 پیدا می‌شود که \varepsilon بهینه است.
اولین مسئله را می‌توان توسط یک محاسبه کوتاه‌ترین مسیر مبدأ واحد در (G_f, c') حل کرد که c' از روی c' با اضافه کردن \varepsilon به هر وزن یال به دست می‌آیدو گولدبرگ پیشنهاد کرد که محاسبهٔ کوتاهترین مسیر در هر تکرار انجام گیرد یعنی چک شود که آیا روند b جاری   بهینه است یا خیر و تنها در صورت منفی بودن جواب refine صدا زده شود.
مکاشفهٔ دیگر توسط راه حل مسئله دوم به دست می‌آید. این احتمال گولد برگ و تارجان، و گولدبرگ و همکارانش، مورد اشاره قرار گرفته اما بیشتر دنبال نشده‌است. ملاحظه کنید که f ،\varepsilon بهینه است اگر هیچ مدار جهت دار از مجموع وزن منفی در (G_f, c') وجود نداشته باشد که در آن c'(e):=c(e)+\varepsilon برای همه ی
e \in E(G_f) . لذا کوچکترین \varepsilon که به ازای آن \varepsilon بهینه می‌شود عبارت است از-\mu که در آن \mu عبارت است از کمترین وزن میانگین مدار جهت دار در (G_f, c).
لذا مسئله دوم چیری به جز یک مسئله کمترین چرخهٔ میانگین نیست. این مسئله را می‌توان توسط یک الگوریتم پارامتری کوتاه‌ترین مسیر به‌طور بسیار کارآند حل کرد. یک نسخهٔ پایه توسط کارپ و ارلین و اشنایدر توصیف شده و نسخهٔ بهبود یافتهٔ آن توسط تارجان و ارلین بیان شده‌است. یک پیاده‌سازی کارآمد این الگوریتم توسط بوناگل توصیف شده‌است. زمان اجرا در بدترین حالت عبارت است از O(nm + n^2log(n)).
برای پیاده‌سازی الگوریتم روند کمترین هزینه، ما مسئله دوم را با استفاده از محاسبه پارامتری کوتاه‌ترین مسیر در هر تکرار حل کردیم. کوچکترین \varepsilon که سبب شود روند b جاری \varepsilon بهینه شود را پیدا می‌کنیم و همچنین یک \pi بالقوه مناسب را میابیم. سپس refine را به f، \pi و
\frac{\varepsilon}{\alpha} اعمال می‌کنیم.
این مکاشفه منجر به بهبود قابل ملاحظه‌ای در زمان اجرا شد. در مقایسه با این که توسط یک محاسبه ساده کوتاه‌ترین مسیر فقط چک شود که آیا روند   بهینه است، ما به بهبود زمان اجرا به میزان 40% دست یافتیم.
سؤال دیگر این است که پارامتر \alpha چه طور انتخاب شود. ملاحظات تئوری مقدار 4 را پیشنهاد می‌کند، 

### پیشگویی push
مکاشفه دیگر به نام پیشگویی push به گولدبرگ منتسب است. هدف آن اجتناب از هل دادن روند از یک راس v به یک همسایه \alpha. است اگر این روند در قدم بعد از آن احتمال دارد مجدداً به v هول داده شود. ما الگوریتم را تغییر می‌دهیم و هل دادن را بیش از A_f(w) := max \{ 0, -e_f(w) + \sum u_f(e) \} واحد از روند به راس w انجام نمی‌دهیم. اگر این عدد مثبت باشد بیانگر تعداد روندهایی است که می‌تواند از \alpha، بدون relabeling هل داده شود.
لازم است رویه relabel را گسترش داد. اگر به اندازه a_f(w)  واحد از v به
w هل داده شود، راس w به عنوان بیش فعال علامت می خورد. پس از آن هیچ روند اضافه‌ای نمی‌تواند به سمت w هل داده شود تا این که w، relabel  شود. به علاوه قبل از relabel  کردن
v، wرا نمی‌توان relabel کرد اما اگر a_f(w) ، آنگاه پس از آن که تمام هل‌های احتمالی از 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)
       \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'-بهینه است. در نتیجه ترکیب با مکاشفه پالایش قیمت توصیف شده در فصل قبل بسیار کارآمد می‌باشد.

### برچسب‌گذاری مجدد کردن
سومین کشف مهم عملیات برچسب‌گذاری مجدد را گسترش می‌دهد به‌طوری‌که رأس‌ها ی زیادی در یک مرحله برچسب‌گذاری مجدد می‌شوند. اگر S یک زیرمجموعه از راس‌هایی باشد که شامل همهٔ رأس‌های بیش از حد منفی باشد، متمم  v(g)/sحداقل یک راس فعال داردو فرض کنید که در گراف مورد قبول از V (G) / S به  Sلبه هم نداریم سپس عملیات برچسب‌گذاری مجدد قابل اجرا است:پتانسیل همهٔ راس‌ها در V (G) / S  را می‌توان به اندازه ɛ کاهش داد.
مشخص است که این عملیات بهینگی ɛ را در f از بین نمی‌برد. این نظریه که در محدوده اعداد push  و عملیات برچسب‌گذاری مجدد است،اگر عملیات برچسب‌گذاری مجدد به کار برده شوند ، تغییر نمی‌کنند و تعداد دفعات ان هم اهمیتی ندارد.(در مثال [2] اثبات شده‌است)

عملیات برچسب‌گذاری مجدد (set_relabel) می‌تواند این‌گونه بازگو شود: 

\text{begin}
procedure relabel global(π)
begin
S := { v∊ V (G) : ef (v)  1000).
برچسب‌گذاری مجدد  از بقیه کم اهمیت تر است اما مواردی هست که با عدم استفاده از هر یک از کشفیات می‌توان زمان اجرا را بسیار بالاتر برد.

## پانویس

## منابع

[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin (1993) Network Flows. Prentice Hall, Engelwood Cli_s

[2] U. Bunnagel (1998) E_ziente Implementierung von Netzwerkalgorithmen. Diploma thesis, University of Bonn

[3] R.G. Busacker, and P.J. Gowen (1961) A Procedure for Determining a Family of Minimum-Cost Network Flow Patterns. O.R.O. Technical Paper 15

[4] J. Edmonds, and R.M. Karp (1972) Theoretical Improvements in Algorithmic E_- ciency for Network Flow Problems. Journal of the ACM 19, 248-264

[5] M.L. Fredman, and R.E. Tarjan (1987) Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34, 596-615

[6] A.V. Goldberg (1992) An E_cient Implementation of a scaling Minimum{Cost Flow Algorithm. Departement of Computer Science, Stanford University, August 1992;
NEC Research Institute, Princeton, October 1992; Journal of Algorithms 22 (1997), 1-29

[7] A.V. Goldberg, and M. Kharitonov (1993) On Implementing Scaling Push-Relabel Algorithms for the Minimum-Cost Flow Problem. In: DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, Vol. 12, 157-198

[8] A.V. Goldberg, and R.E. Tarjan (1988) A New Approach to the Maximum Flow Problem. Journal of the ACM 35, 921-940

[9] A.V. Goldberg, and R.E. Tarjan (1990) Finding Minimum{Cost Circulations by Successive Approximation. Mathematics of Operations Research 15, 430-466

[10] A.V. Goldberg, _E. Tardos, and R.E. Tarjan (1990) Network Flow Algorithms. In: B. Korte, L. Lov_asz, H. J. Promel, A. Schrijver (eds.): Flows, Paths and VLSI Layout, Springer, Berlin, 101-164

[11] M. Iri (1960) A New Method for Solving Transportation-Network Problems. Journal of the Operations Research Society of Japan 3, 27-87

[12] W.S. Jewell (1958) Optimal Flow through Networks. Interim Technical Report 8, MIT

رده:مقاله‌های ایجادشده توسط ایجادگر