مجله تحقیق در عملیات در کاربردهای آن ( ریاضی کاربردی سابق )

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