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

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

کلیدواژه ها:

آرایه سیستالیک ، الگوریتم فلوید ، پیچیدگی زمانی ، موازی کردن الگوریتم فلوید