الگوریتم Push-Relabel
الگوریتم Push-Relabel که توسط اندرو وی. گلدبرگ و رابرت ای. تارژان در سال ۱۹۸۸ توسعه یافت، روشی بسیار کارآمد برای محاسبه حداکثر جریان در شبکهها است. برخلاف روشهای مسیر افزایشی، این الگوریتم یک پیشجریان (preflow) را حفظ میکند و از عملیات محلی push و عملیات سراسری relabel برای هدایت جریان به سمت خروجی (sink) استفاده میکند و به پیچیدگی بدترین حالت (worst-case complexity) برتری دست مییابد.
مطالعهٔ کامل روش
برای خواندن این بخش با حساب رایگان وارد شوید.
Method map
The neighbourhood of related methods — select a node to explore.
منابع
- Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940. DOI: 10.1145/48014.61051 ↗
- Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin. link ↗
نحوهٔ استناد به این صفحه
ScholarGate. (2026, June 3). Push-Relabel Algorithm for Maximum Flow. ScholarGate. https://scholargate.app/fa/operations-research/push-relabel-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- الگوریتم بلمن-فوردپژوهش عملیات↔ compare
- الگوریتم دایکستراپژوهش عملیات↔ compare
- الگوریتم فورد-فالکرسونپژوهش عملیات↔ compare
ارجاعشده در
در این صفحه مشکلی دیدید؟ گزارش دهید یا اصلاحی پیشنهاد کنید →