اصغر عینی - دانشجوی دکتری مهندسی صنایع، دانشگاه صنعتی شریف
کوروش عشقی - استاد دانشکده مهندسی صنایع، دانشگاه صنعتی شریف

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

شبکه های کوتاه ترین مسیر، مسیله کوتاه ترین مسیر، الگوریتم فوید- وارشال، تحلیل حساسیت در شبکه های کوتاه ترین مسیر، کاهش یا افزایش وزن کمان در مسیله کوتاه ترین مسیر