بهبود الگوریتمی برای مساله کوتاه ترین مسیر هر زوج گره با دور منفی

مساله کوتاه ترین مسیر یکی از معروف ترین مسایل در نظریه گراف و شبکه ها می باشد که به دلیل کاربرد فراوان آنتوسط محققان زیادی مورد مطالعه قرارگرفته است. شبکه ها به دو دسته ی بادور و بدون دور تقسیم می شوند.شبکه های دارای دوری که جمع جبری وزن کمان های دور در آن منفی است به شبکه های با دور منفی مرسومهستند. مساله تعیین دور منفی عبارت است از مساله ای که در یک شبکه ی جهت دار برای وجود یک دور منفیتصمیم گیری می نماید. برای مسایل کوتاه ترین مسیر در شبکه های با دور منفی الگوریتم های مختلفی توسعهیافته است، که تمام آنها بر پایه الگوریتم های موجود برای شبکه های کوتاه ترین مسیر بدون دور منفی طراحیشده اند. این مقاله، به بهبود الگوریتم مستطیلی برای تعیین دور منفی در شبکه های کوتاه ترین مسیر با یک دورمنفی، محاسبه پیچیدگی زمانی الگوریتم و نیز پیداکردن وزن دور منفی می پردازد که خود یک مزیت بزرگ درحوزه آموزشی محسوب میگردد. از مزایای این الگوریتم می توان به همگرایی سریعتر و زمان محاسبات کمترنسبت به الگوریتم های موجود در ادبیات اشاره نمود. نحوه به کارگیری الگوریتم در قالب مثال کوچکی مورد بررسیقرار می گیرد.

کلیدواژه ها:

الگوریتم فلوید وارشال ، الگوریتم مستطیلی ، شبکه های کوتاه ترین مسیر دارای دور ، شبکه های کوتاه ترین مسیر با دور منفی