تحلیل و بررسی کارایی اجرای سریال و موازی الگوریتم کوتاه ترین مسیر دایجسترا

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

کلیدواژه ها:

الگوریتم دایجسترا ، کوتاه ترین مسیر ، الگوریتم موازی ، الگوریتم سریال