تعیین دور منفی در شبکه‌های کوتاه‌ترین مسیر

الهه بدیعی¹ اصغر عینی²

1) کارشناسی ارشد مهندسی صنایع- صنایع، دانشگاه آزاد اسلامی واحد تهران شمال، ایران -
2) عضو هیات علمی دانشکده مهندسی صنایع، دانشگاه آزاد اسلامی واحد تهران شمال،ایران-

محل انتشار : دومین کنگره بین المللی علوم، مهندسی و تکنولوژی - هامبورگ(germanconf.com/2nd)
چکیده :
مساله كوتاه‌ترين مسير يكي از معروفترین مسایل در نظریه گراف و شبکه‌‌ها می‌باشد كه به دلیل کاربرد فراوان آن توسط محققان زيادي مورد مطالعه قرار‌گرفته است. شبکه‌ها به دو دسته‌ی با‌دور و بدون‌دور تقسیم می‌شوند. شبکه‌های دارای دوری که جمع جبری وزن کمان‌های دور در آن منفی است به شبکه‌های با دور منفی مرسوم هستند. مساله تعیین دور منفی عبارت‌است از مساله‌ای که در یک شبکه‌ی جهت‌دار برای وجود یک دور منفی تصمیم‌گیری می‌نماید. برای مسایل کوتاه‌ترین مسیر در شبکه‌های با دور منفی الگوریتم‌های مختلفی توسعه یافته‌است، که تمام آن‌ها بر پایه الگوریتم‌های موجود برای شبکه‌های کوتاه‌ترین مسیر بدون دور منفی طراحی شده‌اند. این مقاله، به بهبود الگوریتم مستطیلی برای تعیین دور منفی در شبکههای کوتاه‌ترین مسیر با یک دور منفی، محاسبه پیچیدگی زمانی الگوریتم و نیز پیدا‌کردن وزن دور منفی میپردازد كه خود يك مزيت بزرگ در حوزه آموزشی محسوب می‌گردد. از مزايای این الگوريتم می‌توان به هم‌گرايی سريع‌تر و زمان محاسبات کمتر نسبت به الگوریتم‌های موجود در ادبیات اشاره نمود. نحوه به‌کارگیری الگوریتم در قالب مثال کوچکی مورد بررسی قرار می‌گیرد.
کلمات کلیدی : الگوريتم فلويد وارشال الگوريتم مستطيلي شبكه‌هاي كوتاه‌ترين مسير داراي دور شبکه‌های کوتاه‌ترین مسیر با دور منفی