الگوریتم دینیک ( به انگلیسی: 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
ورودی:
• شبکهٔ ( G= ( V, E و دو راس مبدأ و مقصد s و t
• ظرفیت یال ها : ( ۰≤c i: ( E υ ER → R
در ابتدا شار همهٔ یال های گراف را برابر صفر قرار می دهیم و با استفاده از جستجوی سطح اول ( BFS ) ، گراف تراز L را بدست می آوریم و این مراحل را تکرار می کنیم:
• تا زمانی که در گراف L مسیر افزایشی وجود دارد، مسیری را انتخاب می کنیم و آن را اشباع می کنیم. ( پس از اتمام این مرحله یک شار سدکننده بدست آمده است )
• سپس دوباره، تراز راس ها را حساب می کنیم و گراف 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 تحلیل الگوریتم گراف تراز L را می توان در زمان ( |O ( |E، با استفاده از BFS بدست آورد و پیدا کردن شار سدکننده در هر مرحله در زمان ( O ( VE انجام می شود.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفگراف 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
ورودی:
• شبکهٔ ( G= ( V, E و دو راس مبدأ و مقصد s و t
• ظرفیت یال ها : ( ۰≤c i: ( E υ ER → R
در ابتدا شار همهٔ یال های گراف را برابر صفر قرار می دهیم و با استفاده از جستجوی سطح اول ( BFS ) ، گراف تراز L را بدست می آوریم و این مراحل را تکرار می کنیم:
• تا زمانی که در گراف L مسیر افزایشی وجود دارد، مسیری را انتخاب می کنیم و آن را اشباع می کنیم. ( پس از اتمام این مرحله یک شار سدکننده بدست آمده است )
• سپس دوباره، تراز راس ها را حساب می کنیم و گراف 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 تحلیل الگوریتم گراف تراز L را می توان در زمان ( |O ( |E، با استفاده از BFS بدست آورد و پیدا کردن شار سدکننده در هر مرحله در زمان ( O ( VE انجام می شود.
wiki: الگوریتم دینیک