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

XML English Abstract Print


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

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

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

بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.