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

Publish Year: 1396
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 370

This Paper With 12 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

GERMANCONF01_129

تاریخ نمایه سازی: 26 مرداد 1397

Abstract:

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

Keywords:

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

Authors

اصغر عینی

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

الهه بدیعی

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