الگوریتم Goldberg و Tarjan
ورودی‌های مسئله عبارتند از: هدف: یافته جریان formula_5 است کهformula_6 را مینیمم می‌کند به‌طوری که: formula_7
formula_8 تعریف 1: یک گردش formula_9 شرایط زیر را ارضا می‌کند. در این تعریف جدید، جریان در قوس اولیه formula_13 شرط formula_14 را ارضا می‌کند و هر واحد جریان هزینه formula_15 را تحمیل می‌کند. جریان در قوس معکوس formula_16 شرط formula_17 را ارضا کرده و هزینه formula_18 را برای هر واحد جریان تحمیل می‌کند. هزینه کل برای دو یال با جریان formula_9 برابر formula_20 است. بنابراین بهینه‌سازی هزینه کل برای این گراف جدید معادل بهینه‌سازی هزینه کل برای گراف اولیه است. برای یک جریان formula_9 در گراف formula_22 گراف باقی‌مانده formula_23 را گرافی تعریف می‌کنیم که مجموعه یال‌های آن عبارتند از: formula_24 کران بالای formula_25 را برای یال formula_26 تعریف می‌کنیم. واضح است که formula_27 تعریف 2: یک پتانسیل تابعی است به صورت formula_28 تعریف 3: فرض کنید تابع پتانسیل formula_29 داده شده‌است. هزینه کاهش یافته را به صورت زیر تعریف می‌کنیم: formula_30 آنگاه داریم: formula_31 تعریف 4: هزینه یک دور formula_32 برابر است با: formula_33 تئوری 1: موارد زیر با هم معادلند. تئوری فوق منجر به الگوریتمی برای محاسبه گردش با کمترین هزینه می‌شود. این الگوریتم به صورت زیر است. صحت الگوریتم فوق از تئوری بالا نتیجه می‌شود. اگر هزینه‌ها و ظرفیت‌ها، هر دو صحیح باشند، جریان بهینه formula_9 موجود است به نحوی که formula_13 برای هر formula_45 صحیح است. فرض کنید: formula_46
formula_47 بنابراین هر گردش شدنی دارای هزینه حداکثری formula_48 و هزینه حداقلی formula_49 است. چون حذف یک دور، هزینه گردش را حداقل به اندازه یک واحد کاهش می‌دهد، برای یافتن یک گردش بهینه به حداکثر formula_50 حذف نیاز است. برای رسیدن به این نتیجه‌گیری که الگوریتم فوق شبه چندجمله‌ای است، به دو مورد زیر نیاز داریم. با انتخاب مناسب دوری که در هر مرحله تکرار الگوریتم باید حذف شود، می‌توان یک الگوریتم با زمان چندجمله‌ای به دست آورد. تعریف 5: فرض کنید که هزینه متوسط دور formula_32 برابر با formula_54 باشد که formula_55 هزینه دور و formula_56 تعداد یال‌های موجود در formula_32 است. تعریف 6: فرض کنید گردش formula_9 داده شده باشد و formula_59 هزینه دور با کمترین هزینه متوسط باشد. formula_60 می توان با حذف دور با کمترین هزینه مینیمم، یک الگوریتم چندجمله‌ای به دست آورد. اکنون می‌توانیم الگوریتم زیر را بیان کنیم.
شرط formula_62 معادل داشتن یک دور با هزینه منفی در formula_39 است. برای داشتن یک الگوریتم با زمان چندجمله‌ای، باید بتوانیم دور با هزینه متوسط کمینه را در زمان چندجمله‌ای پیدا کنیم. برای تحلیل الگوریتم فوق، تعدادی اصطلاح را تعریف می‌کنیم. تعریف7: یک گردش formula_9، formula_68-بهینه است اگر تابع پتانسیل formula_29 موجود باشد که برای هر formula_26 داشته باشیم formula_71 واضح است که formula_9، 0-بهینه است؛ اگر و تنها اگر formula_9 یک گردش با کمترین هزینه باشد. برای هر گردش، formula_9، formula_75-بهینه است. زیرا اگر برای هر formula_76 قرار دهیم formula_77؛ برای هر formula_26 داریم formula_79. تعریف 8: formula_80 کمترین formula_68 است که formula_9، formula_68- بهینه باشد. دو مقدار formula_80 و formula_59 به شکل جالبی به هم مرتبطند. تئوری 2: برای یک گردش formula_9 داریم: formula_87 اثبات: ابتدا نشان می‌دهیم formula_88. چون formula_89 با جمع کردن روی تمام یال‌های هر دور formula_32 می‌بینیم که formula_93 حال نشان می‌دهیم که formula_94. قرار می‌دهیم formula_95. آنگاه برای هر دورformula_32 در formula_39 داریم: formula_98 راس formula_99 را به گراف اضافه کرده و و آن را به همه رئوس formula_100، با یال‌هایی به وزن formula_101 وصل می‌کنیم. پتانسیل formula_102 را برای گره formula_100 به صورت طول کوتاه‌ترین مسیر از formula_99 به formula_100 با استفاده از هزینه‌های formula_106 تعریف می‌کنیم. با استفاده از تعریف کوتاهترین مسیر داریم: formula_107 که نتیجه می‌دهد: formula_108 این بدان معنی است که formula_9، formula_110- بهینه است. بنابراین formula_111 فرض کنید گردش formula_9 داده شده باشد و formula_113 گردش به دست آمده بعد از formula_114 بار تکرار الگوریتم حذف دور با کمترین هزینه متوسط روی formula_9 باشد. تئوری زیر ثابت می‌کند که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای اجرا می‌شود. تئوری3: formula_116 تئوری4: formula_117 که formula_118 و formula_119 تعداد یال‌ها و گره‌ها در گراف هستند. تئوری5: اگر formula_120 گردش formula_9 بهینه است. اثبات: این حقیقت که formula_122 نشان می‌دهد که پتانسیل formula_29 موجود است که formula_124. بنابراین برای هر دور formula_125. با توجه به صحیح بودن هزینه‌ها داریم؛ formula_126 حال با توجه به سه نتیجه قبل ثابت می‌کنیم که الگوریتم Goldberg-Tarjan در زمان چندجمله‌ای بر حسب اندازه ورودی، خاتمه می یابد. تئوری6: الگوریتم حذف دور با کمترین هزینه متوسط Goldberg-Tarjan، به حداکثر formula_127 تکرار نیاز دارد. اثبات: هر گردش اولیه C- بهینه است. بعد از formula_128 تکرار، با توجه به اینکه formula_129، داریم: formula_130 اگر محاسبه دور با هزینه متوسط کمینه، زمانی برابر formula_51 داشته باشد، زمان اجرای الگوریتم Goldberg-tarjan برابر formula_132 خواهد بود. البته توجه داشته باشید که این الگوریتم کاملاً چندجمله‌ای نیست. اثبات تئوری 3: می‌دانیم پتانسیل formula_29 موجود است که: formula_134 به علاوه، formula_87. برای دور formula_32 با کمترین هزینه متوسط، چون formula_137، نتیجه می‌گیریم که formula_138. حال ادعا می‌کنیم که formula_139. داریم formula_140، اگر formula_141 یا formula_142. در حالت اول، formula_143. در حالت دوم، formula_144. در هر دو حالت، formula_145، formula_80 -بهینه است و تئوری ثابت می‌شود. اثبات تئوری4: می‌دانیم پتانسیل formula_29 موجود است که formula_134. فرض کنید در تکرار formula_114، دور formula_32 را حذف می‌کنیم که در آن، formula_151. آنگاه formula_152 بنابراین formula_153
حذف دور، یک یال با formula_154 را از گراف باقی‌مانده حذف و تنها یال‌هایی با formula_155 را ایجاد می‌کند. بنابراین برای حذف چنین یالی به بیش از formula_118 تکرار نیاز نیست. انتزاعی الگوریتم هزینه پیمایش گولد برگ (Goldberg) و تارجان(Tarjan)، یکی
از کارآمدترین الگوریتم‌ها، برای روند کمترین هزینهٔ مسائل، شناخته شده‌است. اگر چه بازده آن در عمل، به بسیاری از جوانب اجرا بستگی دارد. علاوه بر این، گنجایش بسیاری از ابتکارات، کارایی آن را شدیدا بهبود می‌بخشد. در این مقاله به شرح جوانب اجرا و کارآمدترین ابتکارات، می پردازیم. همچنین، نتایج تجربی، اثر ابتکارات مختلف ترکیبی را پررنگ می‌کند.
فرض می‌کنیم با تئوری روند شبکه آشنایی داریم و نتایج و نشان‌گذاری استاندارد را استفاده می‌کنیم. برای مثال آهوجا(Ahuja)، مگنانتی(Magnanti)،ارلین(Orlin)را ببینید. در اینجا فقط مهمترین‌ها را ذکر می‌کنیم. مسئله روند کمترین هزینه به این صورت تعریف می‌شود: گراف جهتدار formula_22 با گنجایش formula_158 داده شده‌است: formula_159 ، سنگینی formula_160 و ارزش تعادل formula_161، formula_162 را به عنوان یک روند کمترین روند هزینه بیابید، به‌طوری‌که تابع formula_163 با formula_164 برای همهٔ formula_165‌های عضو formula_166 و formula_167برای همهٔ formula_168‌های عضو formula_169 از قبیل formula_170 که کمترین مقدار یا همان مینیموم می‌باشد formula_171مجموعه‌ای از ورودی‌های را تشکیل می‌دهد. راس formula_168 باقی می‌ماند. واضح است که امکان وجود روند کمترین هزینهٔ مسائل، می‌تواند در برابر محاسبه روند ماکسیموم چک شود ( و در بهترین شرایط روند formula_162 می‌تواند پیدا شود). مسائل روند ماکسیموم آسانترند و خیلی سریعتر از مسائل روند کمترین هزینه حل می‌شوند. نمونه داده شده formula_174 از مسئله روند کمترین هزینه و روند formula_163 با formula_176 برای همهٔ formula_177، ظرفیت باقی‌ماندهٔ یال formula_177 به وسیله formula_179 تعریف می‌شود. علاوه بر این، ما یک یال جدید formula_165 از formula_181 به formula_168 برای هر یال formula_183 در نظر گرفته ایم و formula_184 و formula_185 تعریف کرده ایم. باقی‌مانده گراف formula_34 شامل همه بال‌ها ( قدیمی و جدید) با ظرفیت باقی‌مانده مثبت می‌باشد. معروف است که روند formula_162 از formula_9 بهینه است( کمترین هزینه را دارد) اگر و تنها اگر هیچ جریان مستقیم در formula_34 وزن منفی نداشته باشد. دیاگراف formula_22 داده شده با وزن formula_160، یک ذخیره امکانپذیر در formula_192 است، تابع formula_193 به این صورت که هزینه کاهش یافته formula_194 است که برای هر formula_165 نامنفی عبارت formula_196 برقرار است. یک ذخیره امکانپذیر وجود دارد اگر و تنها اگر هیچ جریان مستقیمی، وزن کل منفی نداشته باشد. این توسط کوتاه‌ترین راه محاسبه منبع واحد قطعی و تصمیم گرفته می‌شود. روند داده شدهformula_197 با formula_176 و ذخیره formula_199، یک گراف مجاز تعریف می‌کنیم که تمام یال‌های formula_34 که هزینهٔ کاهش یافته منفی را دارند، در بر بگیرد. گراف مجاز را با formula_201 معنی می‌کنیم. اگر formula_9 یک روند formula_162 بهینه باشد( برای بعضی از formula_162ها) و formula_205 یک ذخیره امکانپذیر در formula_34 باشد، پس مارپیچ است. یک روند formula_162، formula_68 -بهینه نامیده می‌شود اگر یک ذخیره formula_193 مانند formula_210 برای همهٔ formula_211. پس بهینه 0 هیچ چیز نیست ولی بهینه است. الگوریتم هزینه پیمایش گولبرگ و تارجان یک روند formula_162 را محاسبه می‌کند که بهینه formula_68 برای بعضی از formula_68‌های بزرگ است. پس مقدار formula_68 را در هر تکرار، نگهداری کردن و بهینگی formula_68، کاهش می‌دهد. ساده است که هر روند formula_162، بهینه formula_68 است اگر formula_219 . علاوه بر این، از دید هزینه‌های انتگرال، هر روند formula_68-بهینه با formula_221، بهینه است.
پس ساختار جهانی این الگوریتم، به صورت زیر است.
این روال دستوری( مجموعه کد) به صورت زیر اجرا می‌شود: ابتدا مقدار ممکن ماکسیموم از رونددر طول همهٔ یال‌ها با هزینه کاهش یافته منفی هل داده می‌شود. این نتیجه یک روند formula_233 بهینه برای بعضی formula_233‌ها است. یک راس فعال نامیده می‌شود اگر اضافی باشد. formula_235 تا زمانی که حتی یک راس فعال وجود داشته باشد، چه relabel یا چه push، به جای راس فعال اجرا می‌شود.
هر اجرای refine، formula_259 عمل relabel و formula_260. عمل push استفاده می‌کند که formula_261 و formula_262. اثبات این موارد قبلاً ذکر شده‌است.
برای محاسبه روند formula_162 اولیه، الگوریتم روند ماکسیموم گولدبرگ و تارجان استفاده می‌شود. در آزمایش‌های ما فقط بخش کوچکی از زمان اجرا برای این قدم اولیه مصرف شد. تصمیم اولیه در هنگام پیاده‌سازی الگوریتم فوق مربوط به گراف باقی مانده‌ای است: لازم نیست که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم. اما اگر بدون ذخیره‌سازی عمل شود، لازم است تمام یال‌های همسایهٔ یک راس فعال چک شود قبل از این کع بتوان آن را relabel کرد. این کار بسیار پر هزینه است. لذا تصمیم گرفتیم که گراف باقی مانده‌ای را به‌طور صریح ذخیره کنیم به وجودی که لازم است بعد از هر عمل push آن را به روز کنیم. ظرفیت باقی مانده‌ای ذخیره و در هر یال به روز می‌شود. در نتیجه نیازی به ذخیره روند نیست. در حقیقت روند به‌طور صریح مورد نیاز نیست مگر در زمان باز گرداندن خروجی بعد از پایان الگوریتم. برای هر راس formula_168،افزونگی formula_266 و formula_267 احتمالی ذخیره می‌شود. هزینه‌های کاهش یافته به‌طور صریح ذخیره نمی‌شوند چون مشخص گردید که به صرفه تر است که هر گاه که مورد نیاز بودند مجدداً محاسبه شوند. برای هر راس لیستی از یال‌های خارج شونده با ظرفیت باقی مانده‌ای مثبت موجود است. اشاره‌گری داریم که برای هر راس فعال عنصر جاری در این لیست را نشانه‌گذاری می‌کند. هرگاه یک push یال جاری را اشباح کند( یا وقتی که الگوریتم مشخص می‌کند که یال جاری دارای هزینه کاهش یافته غیر منفی است) اشاره گر به جلو حرکت می‌کند. این امر متضمن آن است که یک relabel می‌تواند زمانی که اشاره گر به انتهای لیست می‌رسد انجام پذیرد. یک امر مهم در پیاده‌سازی انتخاب راس فعال است. با توجه به این که تعداد رأس‌های فعال معمولاً کم است لازم است که ساختمان داده‌ای استفاده شود که مجموعه گره‌های فعال را در بر دارد. ساختمان داده‌های ساده یا یک صف یا یک پشته هستند. راه پیچیده تر عبارت است از ذخیره کردن رأس‌های فعال به صورت یک ترتیب مبتنی بر همبندی نسبت به گراف قابل تصدیق ( که غیر چرخه‌ای است). اما در عمل تعداد عملیات pushو relabel اندکی بزرگتر از حالتی است که از پیاده‌سازی ساده صف استفاده می‌شود. به علاوه انتخاب اولین راس با ترتیب مبتنی بر همبندی پر هزینه تر است حتی موقعی که از کارآمدترین ساختمان داده، دنباله فیبوناچی استفاده شود. با توجه به این ملاحظات تصمیم گرفتیم که رأس‌های فعال را در یک صف ساده ذخیره کنیم. توجه شود که این رویکرد مرز تئوری بر روی تعداد عملیات push را برای هر بار اجرای refine به formula_268 کاهش می‌دهد. رویه refine یک روند formula_162 ،formula_68-بهینه محاسبه می‌کند. از طرفی بسیار اتفاق میافتد که این روند از قبل برای بعضی از formula_271 بهینه برای بعضی از formula_272. در این صورت ممکن است بتوانیم از بعضی تکرارها بدون اجرای refine صرف نظر کنیم در نتیجه دو سؤال مطرح می‌شود اولین مسئله را می‌توان توسط یک محاسبه کوتاه‌ترین مسیر مبدأ واحد در formula_285 حل کرد که formula_286 از روی formula_286 با اضافه کردن formula_68 به هر وزن یال به دست می‌آیدو گولدبرگ پیشنهاد کرد که محاسبهٔ کوتاهترین مسیر در هر تکرار انجام گیرد یعنی چک شود که آیا روند formula_162 جاری بهینه است یا خیر و تنها در صورت منفی بودن جواب refine صدا زده شود. مکاشفهٔ دیگر توسط راه حل مسئله دوم به دست می‌آید. این احتمال گولد برگ و تارجان، و گولدبرگ و همکارانش، مورد اشاره قرار گرفته اما بیشتر دنبال نشده‌است. ملاحظه کنید که formula_9 ،formula_68 بهینه است اگر هیچ مدار جهت دار از مجموع وزن منفی در formula_285 وجود نداشته باشد که در آن formula_293 برای همه ی formula_278 . لذا کوچکترین formula_68 که به ازای آن formula_68 بهینه می‌شود عبارت است ازformula_297 که در آن formula_298 عبارت است از کمترین وزن میانگین مدار جهت دار در formula_299. لذا مسئله دوم چیری به جز یک مسئله کمترین چرخهٔ میانگین نیست. این مسئله را می‌توان توسط یک الگوریتم پارامتری کوتاه‌ترین مسیر به‌طور بسیار کارآند حل کرد. یک نسخهٔ پایه توسط کارپ و ارلین و اشنایدر توصیف شده و نسخهٔ بهبود یافتهٔ آن توسط تارجان و ارلین بیان شده‌است. یک پیاده‌سازی کارآمد این الگوریتم توسط بوناگل توصیف شده‌است. زمان اجرا در بدترین حالت عبارت است از formula_300. برای پیاده‌سازی الگوریتم روند کمترین هزینه، ما مسئله دوم را با استفاده از محاسبه پارامتری کوتاه‌ترین مسیر در هر تکرار حل کردیم. کوچکترین formula_68 که سبب شود روند formula_162 جاری formula_68 بهینه شود را پیدا می‌کنیم و همچنین یک formula_205 بالقوه مناسب را میابیم. سپس refine را به formula_9، formula_205 و formula_307 اعمال می‌کنیم. این مکاشفه منجر به بهبود قابل ملاحظه‌ای در زمان اجرا شد. در مقایسه با این که توسط یک مخاسبه ساده کوتاه‌ترین مسیر فقط چک شود که آیا روند بهینه است، ما به بهبود زمان اجرا به میزان 40% دست یافتیم. سؤال دیگر این است که پارامتر formula_222 چه طور انتخاب شود. ملاحظات تئوری مقدار 4 را پیشنهاد می‌کند،
مکاشفه دیگر به نام پیشگویی push به گولدبرگ منتسب است. هدف آن اجتناب از هل دادن روند از یک راس formula_168 به یک همسایه formula_222. است اگر این روند در قدم بعد از آن احتمال دارد مجدداً به formula_168 هول داده شود. ما الگوریتم را تغییر می‌دهیم و هل دادن را بیش از formula_312 واحد از روند به راس formula_181 انجام نمی‌دهیم. اگر این عدد مثبت باشد بیانگر تعداد روندهایی است که می‌تواند از formula_222، بدون relabeling هل داده شود. لازم است رویه relabel را گسترش داد. اگر به اندازه formula_315 واحد از formula_168 به formula_181 هل داده شود، راس formula_181 به عنوان بیش فعال علامت می خورد. پس از آن هیچ روند اضافه‌ای نمی‌تواند به سمت formula_181 هل داده شود تا این که formula_181، relabel شود. به علاوه قبل از relabel کردن formula_168، formula_181را نمی‌توان relabel کرد اما اگر formula_323، آنگاه پس از آن که تمام هل‌های احتمالی از formula_181 انجام گرفته باشد formula_181 فعال نخواهد بود. این موضوع نشان می‌دهد که لازم است عمل relabel به رأس‌های بیش فعال گسترش داده شود. مستقل از این که آیا این رأس‌ها فعالند یا خیر. گولدبرگ و خاریتونوف نیز پیشنهاد می‌دهند که رویه relabel به صورت فوق ذکر به رأس‌های پیش فعال اغمال شود با این فرق که در مواردی که هیچ یال باقی مانده‌ای راس relabel را ترک نمی‌کند، این احتمال به اندازه formula_68 کاهش یابد. ما رویه relabel متفاوت زیر را پیاده‌سازی کردیم.
دلیل ما برای انتخاب رویه relabel گسترش یافته آن است که نا را قادر می‌سازد که مقدار بیشینه قدر مطلق مقادیر بالقوه را محدود کنیم. این موضوع به دلایل عددی مهم است. در هنگام بررسی یک راس بیش فعال formula_168 امکان دارد راس دیگری مانند formula_181 بیش فعال گردد. اگر رأس‌های بیش فعال در داخل یک پشته قرار دهیم و همیشه آخرین راس بیش فعال اضافه شده را در نظر داشته باشیم می‌توان این رأس‌ها را با ترتیب سریع بررسی کرد.( توجه شود که گراف قابل تصدیق فاقد چرخه است). رویه بازگشتی زیر این موضوع را منعکس می‌کند.
تعداد عمل‌های relabel که به هر راس اعمال می‌شود را کماکان می‌توان به formula_369 محدود کرد. در عمل تعداد عمل‌های relabel تقریباً ثابت می‌ماند در حالی که تعداد عمل‌های push به اندازه 40-60% کاهش می یابد. به علاوه روند محاسبه شده توسط رویه refine جدید معمولاً بهتر است یعنی برای formula_271 کوچکتری formula_271-بهینه است. در نتیجه ترکیب با مکاشفه پالایش قیمت توصیف شده در فصل قبل بسیار کارآمد می‌باشد.
سومین کشف مهم عملیات برچسب‌گذاری مجدد را گسترش می‌دهد به‌طوری‌که رأس‌ها ی زیادی در یک مرحله برچسب‌گذاری مجدد می‌شوند. اگر S یک زیرمجموعه از راس‌هایی باشد که شامل همهٔ رأس‌های بیش از حد منفی باشد، متمم v(g)/sحداقل یک راس فعال داردو فرض کنید که در گراف مورد قبول از V (G) / S به Sلبه هم نداریم سپس عملیات برچسب‌گذاری مجدد قابل اجرا است:پتانسیل همهٔ راس‌ها در V (G) / S را می‌توان به اندازه ɛ کاهش داد. مشخص است که این عملیات بهینگی ɛ را در f از بین نمی‌برد. این نظریه که در محدوده اعداد push و عملیات برچسب‌گذاری مجدد است،اگر عملیات برچسب‌گذاری مجدد به کار برده شوند ، تغییر نمی‌کنند و تعداد دفعات ان هم اهمیتی ندارد.(در مثال [2] اثبات شده‌است)
عملیات برچسب‌گذاری مجدد (set_relabel) می‌تواند این‌گونه بازگو شود:
formula_224 procedure relabel global(π) begin S := { v∊ V (G) : ef (v) < 0}; while V (G) \ S contains an active vertex do begin Add all vertices to S from which S can be reached in G f; if V (G) \ S contains an active vertex then π(v) := π (v) - ɛ for all v ∊V (G) \ S; end; end;
این روش می‌تواند به صورت کارامدی توسط ساختار سطلی (bucket structure) انجام شود. سطل‌ها با اعداد صحیح نامنفی نشان داده می‌شوند. اولین سطل به شماره B(v) به هر راس v اختصاص داده می‌شود برای اینکه سطل حاوی v یا ∞را (در صورتی‌که v در هیچ‌کدام از سطل‌ها قرار نگرفته باشد) نشان دهد. در نهایت B(v) شماره عملیات برچسب‌گذاری مجدد خواهد شد که برای راس v به کار برده می‌شود. ابتدا همهٔ رأس‌ها ی منفی در سطل با مقدار صفر قرار می‌گیرند و بقیه سطل‌ها خالی می‌مانند. سپس سطل‌ها به این شکل بررسی می‌شوند: برای هر سطل i، به‌طوری‌که i=1,2,…. و هر راس v به صورت B(v) = i و هر لبهٔ e=(w,v)به عنوان عضوی از Gf ، راس w از B(w) حذف می‌شود. اگر k بزرگترین سطل نشان دهنده راس فعال باشد، پتانسیل هر راس v اندازه ɛ کم می‌شودmin(B(v), k). اگر این بعد از هر n بار عملیات عادی برچسب‌گذاری مجدد استفاده شود، بدترین حالت زمان اجرای بهبود بخشیدن تغییر نمی‌کند. تعداد عملیات برچسب‌گذاری مجدد (همان عدد k) در طول برچسب‌گذاری مجدد کلی( (relabel global برابر O(n) است. بنابراین تعداد کل عملیات برچسب‌گذاری مجدد در طول بهبود بخشیدن O(n2) است. به‌طور تجربی، کشف برچسب‌گذاری مجدد ، تعداد عملیات را کاهش می‌دهد . کار اضافه برای روش
5)نتایج تجربی نتایجی روی IBMRS/6000Mod .550 workstations. به دست آمده‌است ، با دو ویژگی سر وکار داریم: اولین گروه توسط NETGEN تولید می‌شوند٫ابزاریست که توسط Klingmanو Napier توسعه داده شده‌است. ابتدا یک مولد، منبعی را تولید می‌کند و سپس یک شبکه یدک شامل لبه‌های با ظرفیت بالا را می‌سازد برای اینکه از امکان ان اطمینان حاصل شود. سپس لبه هارا به صورت رندم اضافه می‌کند. گروه شامل 35 شبکه با 200 تا 8000 راس است. دومین گروه شامل مشکلات ناشی از فاز دادن در طرح VLSI است. این شبکه ها خیلی پراکنده‌اند. تعداد لبه‌ها فقط 2-3برابر تعداد رأس‌ها است. گروه شامل 570 شبکه است. تعداد رأس‌ها بین 10 تا 1000 است. چون تفاوت‌های ناچیزی در نتایج محاسبه شده بین دو کلاس داریم، باید خودمان را به حالت دوم محدود کنیم چون حالت اول مشکلات بیشتری دارد. محاسبه اولیه در الگوریتم Goldberg و Tarjan در اکثر مواقع کمتر از %1 از زمان اجرای کل است. اجرای این اکتشاف‌ها برای اینکه الگوریتم Goldberg-Tarjan رقابتی شوند بسیار مفید است. با این کشفیات کوتاه‌ترین مسیر الگوریتم موفق به دست می اید. به هر حال ما باید بیان کنیم که نمونه‌هایی هم داریم که از مسیرهای کوتاه الگوریتم Goldberg-Tarjan بهتر است. هر اکتشافی پیشرفت قابل توجهی از تعداد عملیات برچسب‌گذاری مجدد و pushرا می‌دهد و زمان اجرا به وضوح به این عملیات‌ها بستگی دارد. کشف push-look-ahead اثر قابل توجهی روی تعداد عملیات push دارد:وقتی در الگوریتم پایه این تعداد تقریباً دوبرابرتعداد عملیات برچسب‌گذاری مجدد است، فرکانس هر دو عملیات هنگام استفاده از push-look-ahead برابر می‌شود. استفاده زیاد از برچسب‌گذاری مجدد می‌تواند زمان اجرا را برای اعداد بزرگ کاهش دهد (n> 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