بهینه سازی در شبکه های حداکثر جریان هرزوج گره

شبکه های حداکثر جریان از مباحث مشهور، بنیادی و پرطرف دار در جریان های شبکه بوده و کاربردهای فراوانی در حوزه های مختلف دارند. برای حل اینگونه شبکه ها، روش ها و الگوریتم های زیادی با رویکردهای متفاوت جریان دارد. در این مقاله، الگوریتم دقیق جدیدی با نام مستطیل آبشاری، با رویکرد افزودن مسیر بر پایه جبرماتریسی و با پیچیدگی زمانی بدترین حالت ((O(n(3 ارایه می شود، بطوریکه مقدار حداکثر جریان و مسیر را از هرزوج گره محاسبه می کند. اساس این الگوریتم، انجام حداقل n-2 محاسبات ریاضی در قالب مستطیل هایی هستند که در یک راس مشترکند. الگوریتم مستطیل های آبشاری، بجهت وابسته کردن محاسبات ماتریس مسیر به ماتریس جریان بسیار سریع و از طرفی دیگر بجهت انجام محاسبات مستطیلی بسیار جذاب است. در پایان، با ارایه یک مثال نمونه الگوریتم مستطیل های آبشاری گام به گام پیاده سازی شده است.

کلیدواژه ها:

شبکه های حداکثر جریان ، الگوریتم های شبکه های حداکثر جریان ، الگوریتم های مسیر افزودنی ، الگوریتم های پیش جریان فشاری ، الگوریتم مستطیل آبشاری