From Wikipedia, the free encyclopedia
الگوریتم دینیک (به انگلیسی: Dinic's algorithm) یک الگوریتم چندجملهای برای محاسبه شار بیشینه از s به t در یک گراف جهتدار است که در سال ۱۹۷۰ توسط Yefim Dinitz ارائه شد و همانند الگوریتم ادموندز-کارپ از مسیر افزایشی برای یافتن شار بیشینه استفاده میکند.
گراف G=(V,E,s,t) یک گراف با راس مبدأ s و راس مقصد t و c(u,v), f(u,v) به ترتیب شار و ظرفیت یال (u,v) در گراف G هستند.
ظرفیت پسماند Residual Capacity) cf): یک تابع V×V → R است به طوری که:
اگر (u,v) عضو یالهای گراف G باشد،
(cf(u,v) = c(u,v)-f(u,v
(cf(v,u) = f(u,v
و در غیر اینصورت:
cf(u,v) = ۰
گراف پسماند (Residual Graph): گراف پسماند R=(V,Ef,s,t) را اینگونه تعریف میکنیم:
{ Ef={ (u,v) in E | cf(u,v)> 0
شار سد کننده: به یک شار سدکننده میگویند، اگر همهٔ مسیرهای از s به t آن دارای یال اشباع شده باشند.
تراز راس ((Level(v): فاصله کوتاهترین مسیر از s به v در گراف پسماند R.
در این الگوریتم، یافتن مسیرهای افزایشی را فقط به یالهایی محدود میکنیم که اختلاف تراز آنها ۱ باشد. به همین دلیل زیر گرافی از R را میسازیم که دارای این ویژگی باشد:
گراف تراز L: زیر گرافی از گراف R که برای هر یال(u,v) در آن داشته باشیم: level(v) = level(u) + 1
ورودی:
در ابتدا شار همهٔ یالهای گراف را برابر صفر قرار میدهیم و با استفاده از جستجوی سطح اول(BFS)، گراف تراز L را بدست میآوریم و این مراحل را تکرار میکنیم:
این مراحل را تا زمانی ادامه میدهیم که level(t)<n شود.
1 Input: 2 a flow network G=(V,E,c,s,t) 3 a feasible flow f in G(equal to zero by default) 4 Construct level graph L for f by Breadth First Search 5 By augmentations, find blocking flow f ' in L from f. 6 for all e assign f(e)←f(e)+f'(e) 7 if t is not in level graph, 8 then return f 9 else go to [4]
گراف تراز L را میتوان در زمان(|O(|E، با استفاده از BFS بدست آورد و پیدا کردن شار سدکننده در هر مرحله در زمان (O(VE انجام میشود.
پس از حداکثر n-1 بار اجرای مرحله ۱و۲ (پیدا کردن شار سد کننده)، f برابر شار بیشینه گراف G خواهد بود.
در هر مرحله، تراز راس t حداقل ۱ واحد افزایش پیدا میکند و چون هیچ مسیری با طول بیشتر از ۱-n وجود ندارد، حداکثر ۱-n مرحله برای پیدا کردن شار بیشینه لازم است.
پس زمان اجرای کل الگوریتم (O(V2E میباشد.
در گراف واحد، ظرفیت همهٔ یالهای برابر ۱ است و هر راسی به جز راس مبدأ و مقصد، دقیقاً یک یال ورودی و یک یال خروجی دارد. مرتبه زمانی اجرای این الگوریتم روی گرافهای واحد،(O(mn1/2 است. پیدا کردن شار سدکننده در زمان (O(E قابل انجام است و تعداد مراحل پیدا کردن شار سد کننده،(O(√n-2 است. این الگوریتم، همان الگوریتم هاپکرافت-کارپ برای پیدا کردن تطابق بیشینه در یک گراف دوبخشی است.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.