الگوریتم دینیک

الگوریتم دینیک (به انگلیسی: 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) c_f): یک تابع V×V → R است به طوری که:

اگر (u,v) عضو یال‌های گراف G باشد،

(c_f(u,v) = c(u,v)-f(u,v

(c_f(v,u) = f(u,v

و در غیر اینصورت:

c_f(u,v) = 0

گراف پسماند (Residual Graph) : گراف پسماند R=(V,E_f,s,t) را اینگونه تعریف می‌کنیم:

{ E_f={ (u,v) in E | c_f(u,v) > 0

شار سد کننده: به یک شار سد کننده می‌گویند، اگر همه ی مسیر‌های از s به t آن دارای یال اشباع شده باشند.

تراز راس ((Level(v) : فاصله کوتاه ترین مسیر از s به v در گراف پسماند R.

در این الگوریتم، یافتن مسیر‌های افزایشی را فقط به یالهایی محدود می‌کنیم که اختلاف تراز آنها ١ باشد.به همین دلیل زیر گرافی از R را می‌سازیم که دارای این ویژگی باشد:

گراف تراز L : زیر گرافی از گراف R که برای هر یال(u,v) در آن داشته باشیم: level(v) = level(u) + 1

الگوریتم

ورودی :

• شبکه ی (G=(V,E و دو راس مبدا و مقصد s و t

• ظرفیت یال‌ها :(0≤c _i : (E υ E^R → R

در ابتدا شار همه ی یال‌های گراف را برابر صفر قرار می‌دهیم و با استفاده از جست و جوی سطح اول(BFS)، گراف تراز L را بدست می‌آوریم و این مراحل را تکرار می‌کنیم:

1. تا زمانی که در گراف L مسیر افزایشی وجود دارد، مسیری را انتخاب می‌کنیم و آن را اشباع می‌کنیم.(پس از اتمام این مرحله یک شار سد کننده بدست آمده‌است.)
2. سپس دوباره، تراز راس‌ها را حساب می‌کنیم و گراف 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(V²E می‌باشد.

الگوریتم Dinic برای گراف‌های واحد

در گراف واحد، ظرفیت همه ی یال‌های برابر ١ است و هر راسی به جز راس مبدا و مقصد، دقیقاً یک یال ورودی و یک یال خروجی دارد. مرتبه زمانی اجرای این الگوریتم روی گراف‌های واحد،(O(mn^1/2 است. پیدا کردن شار سد کننده در زمان (O(E قابل انجام است و تعداد مراحل پیدا کردن شار سد کننده،(O(√n-2 است. این الگوریتم، همان الگوریتم هاپکرافت-کارپ برای پیدا کردن تطابق بیشینه در یک گراف دوبخشی است.

منابع

• Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version". In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman. Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218–240. ISBN 978-3540328803. http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf. 

• Tarjan, R. E. (1983). Data structures and network algorithms.