الگوریتم Goldberg و Tarjan
3- حذف دور با کمترین هزینه متوسط

با انتخاب مناسب دوری که در هر مرحله تکرار الگوریتم باید حذف شود، می‌توان یک الگوریتم با زمان چندجمله‌ای به دست آورد.

تعریف 5: فرض کنید که هزینه متوسط دور  \Gamma  برابر با  {\frac {c(\Gamma )}{|\Gamma |}} باشد که
 c(\Gamma ) هزینه دور و  |\Gamma | تعداد یال‌های موجود در  \Gamma  است.

تعریف 6: فرض کنید گردش  f  داده شده باشد و  \mu (f) هزینه دور با کمترین هزینه متوسط باشد.
 \mu (f)=min{\frac {c(\Gamma )}{|\Gamma |}}_{cycles\Gamma \subseteq A_{f}}

می توان با حذف دور با کمترین هزینه مینیمم، یک الگوریتم چندجمله‌ای به دست آورد. اکنون می‌توانیم الگوریتم زیر را بیان کنیم.
فرض کنید  f یک گردش باشد
تا زمانی که  \mu (f)<0
دور  \Gamma  با کمترین هزینه متوسط را حذف کن.  f را به روز رسانی کن
شرط  \mu (f)<0 معادل داشتن یک دور با هزینه منفی در  A_{f} است. برای داشتن یک الگوریتم با زمان چندجمله‌ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله‌ای پیدا کنیم.

برای تحلیل الگوریتم فوق، تعدادی اصطلاح را تعریف می‌کنیم.

تعریف7: یک گردش  f،  \varepsilon -بهینه است اگر تابع پتانسیل  p موجود باشد که برای هر   (i,j)\in A_{f} داشته باشیم  c_{ij}^{p}\geq -\varepsilon 

واضح است که  f، 0-بهینه است؛ اگر و تنها اگر  f یک گردش با کمترین هزینه باشد. برای هر گردش،
 f،  C-بهینه است. زیرا اگر برای هر  i\in V قرار دهیم  p_{i}=0؛ برای هر
 (i,j)\in A_{f} داریم  c_{ij}^{p}\geq -C.

تعریف 8:  \varepsilon (f) کمترین  \varepsilon  است که  f،  \varepsilon - بهینه باشد.

دو مقدار  \varepsilon (f) و  \mu (f) به شکل جالبی به هم مرتبطند.

تئوری 2: برای یک گردش  f داریم:  \mu (f)=-\varepsilon (f)

اثبات: ابتدا نشان می‌دهیم  \mu (f)\geq -\varepsilon (f).

چون

 \exists p:c_{ij}^{p}\geq -\varepsilon (f)\forall (i,j)\in A_{f}

با جمع کردن روی تمام یال‌های هر دور  \Gamma  می‌بینیم که
c^{p}(\Gamma )\geq \varepsilon (f)|\Gamma |. بنابراین برای دور با هزینه متوسط کمینه  \Gamma  داریم:
\mu (f)={\frac {c\left(\Gamma \right)}{|\Gamma |}}={\frac {c^{p}\left(\Gamma \right)}{|\Gamma |}}\geq -\varepsilon (f)

حال نشان می‌دهیم که  \mu (f)\leq -\varepsilon (f).

قرار می‌دهیم  {\bar {c}}_{ij}=c_{ij}-\mu (f). آنگاه برای هر دور \Gamma  در  A_{f} داریم:

 {\bar {c}}(\Gamma )=c(\Gamma )-|\Gamma |\mu (f)\geq c(\Gamma )-|\Gamma |{\frac {c(\Gamma )}{|\Gamma |}}=0

راس  s را به گراف اضافه کرده و و آن را به همه رئوس  i، با یال‌هایی به وزن  c_{si}=0 وصل می‌کنیم. پتانسیل  p_{i} را برای گره  i به صورت طول کوتاه‌ترین مسیر از  s به  i با استفاده از هزینه‌های  {\bar {c}}_{ij} تعریف می‌کنیم. با استفاده از تعریف کوتاهترین مسیر داریم:

 \forall (i,j)\in A_{f},p_{j}\leq 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}\geq \mu (f)

این بدان معنی است که  f،  -\mu (f)- بهینه است. بنابراین  \varepsilon (f)\leq -\mu (f)

فرض کنید گردش  f داده شده باشد و  f^{(k)} گردش به دست آمده بعد از  k بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی  f باشد. تئوری زیر ثابت می‌کند که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای اجرا می‌شود.

تئوری3:  \varepsilon \left(f^{(1)}\right)\geq \varepsilon (f)

تئوری4:  \varepsilon \left(f^{(m)}\right)\geq \left(1-{\frac {1}{n}}\right)\varepsilon (f)

که  m و  n تعداد یال‌ها و گره‌ها در گراف هستند.

تئوری5: اگر  \varepsilon (f)\geq {\frac {1}{n}} گردش  f بهینه است.

اثبات: این حقیقت که  \varepsilon (f)\leq {\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 )\geq 0

حال با توجه به سه نتیجه قبل ثابت می‌کنیم که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای بر حسب اندازه ورودی، خاتمه می یابد.

تئوری6: الگوریتم حذف دور با کمترین هزینه متوسط Goldberg-Tarjan، به حداکثر  O(mn\log(nC)) تکرار نیاز دارد.

اثبات: هر گردش اولیه C- بهینه است. بعد از  mn\log(nC) تکرار، با توجه به اینکه
 \left(1-{\frac {1}{n}}\right)^{n}<e^{-1}، داریم:
 \varepsilon \left(f^{(k)}\right)\leq \left(1-{\frac {1}{n}}\right)^{n\log(nC)}<e^{-\log(nC)}C={\frac {1}{n}}

اگر محاسبه دور با هزینه متوسط کمینه، زمانی برابر  O(mn) داشته باشد، زمان اجرای الگوریتم Goldberg-tarjan برابر
 O\left(m^{2}n^{2}\log(nC)\right) خواهد بود. البته توجه داشته باشید که این الگوریتم کاملاً چندجمله‌ای نیست.

اثبات تئوری 3: می‌دانیم پتانسیل  p موجود است که:

 \forall (i,j)\in A_{f}:c_{ij}^{p}\geq -\varepsilon (f)

به علاوه،  \mu (f)=-\varepsilon (f). برای دور  \Gamma  با کمترین هزینه متوسط، چون
 \mu (f)={\frac {c^{p}(\Gamma )}{|\Gamma |}}، نتیجه می‌گیریم که
 \forall (i,j)\in \Gamma ,c_{ij}^{p}\geq -\varepsilon (f). حال ادعا می‌کنیم که
 \forall (i,j)\in A_{f^{(1)}}:c_{ij}^{p}\geq -\varepsilon (f). داریم  (i,j)\in A_{f^{(1)}}، اگر
 (i,j)\in A_{f} یا  (j,i)\in \Gamma . در حالت اول،  c_{ij}^{p}\geq -\varepsilon (f). در حالت دوم،  c_{ij}^{p}=c_{ji}^{p}=\varepsilon (f)\geq 0. در هر دو حالت،  f^{(1)}،
 \varepsilon (f) -بهینه است و تئوری ثابت می‌شود.

اثبات تئوری4: می‌دانیم پتانسیل  p موجود است که
 \forall (i,j)\in A_{f}:c_{ij}^{p}\geq -\varepsilon (f). فرض کنید در تکرار  k، دور  \Gamma  را حذف می‌کنیم که در آن،
 \exists (i,j)\in \Gamma :c_{ij}^{p}\geq 0. آنگاه

 \varepsilon \left(f^{(k)}\right)=\mu \left(f^{(k)}\right)={\frac {c^{p}(\Gamma )}{|\Gamma |}}\geq {\frac {|\Gamma |-1}{|\Gamma |}}\left(-\varepsilon (f)\right)\geq \left(1-{\frac {1}{n}}\right)(-\varepsilon (f))

بنابراین
 \varepsilon \left(f^{(k)}\right)\leq \left(1-{\frac {1}{n}}\right)(\varepsilon (f))
حذف دور، یک یال با  c_{ij}^{p}<0 را از گراف باقی‌مانده حذف و تنها یال‌هایی با  c_{ij}^{p}>0 را ایجاد می‌کند. بنابراین برای حذف چنین یالی به بیش از  m تکرار نیاز نیست.
انتزاعی

الگوریتم هزینه پیمایش گولد برگ (Goldberg) و تارجان(Tarjan)، یکی از کارآمدترین الگوریتم‌ها، برای روند کمترین هزینهٔ مسائل، شناخته شده‌است. اگر چه بازده آن در عمل، به بسیاری از جوانب اجرا بستگی دارد. علاوه بر این، گنجایش بسیاری از ابتکارات، کارایی آن را شدیدا بهبود می‌بخشد. در این مقاله به شرح جوانب اجرا و کارآمدترین ابتکارات، می پردازیم. همچنین، نتایج تجربی، اثر ابتکارات مختلف ترکیبی را پررنگ می‌کند.