دوره 14، شماره 4 - ( 9-1396 )                   جلد 14 شماره 4 صفحات 67-87 | برگشت به فهرست نسخه ها

XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Aini A, Eshghi K. Cascade rectangle algorithm and transposition matrix in the cycled shortest path networks.. Journal of Operational Research and Its Applications. 2017; 14 (4) :67-87
URL: http://jamlu.liau.ac.ir/article-1-1318-fa.html
عینی اصغر، عشقی کورش. الگوریتم مستطیل آبشاری و ماتریس انتقال در شبکه های کوتاه ترین مسیر بادور. تحقیق در عملیات در کاربردهای آن . 1396; 14 (4) :67-87

URL: http://jamlu.liau.ac.ir/article-1-1318-fa.html


دانشگاه صنعتی شریف
چکیده:   (1783 مشاهده)

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

متن کامل [PDF 935 kb]   (546 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: تخصصي
دریافت: 1396/3/18 | پذیرش: 1396/8/19 | انتشار: 1396/10/29

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA

ارسال پیام به نویسنده مسئول