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

یکی از مهمترین کاربردهای سیستمهای اطلاعات مکانی ( GIS ) در زم ینه مدیریت بهینه تسهیلاتی چون حمل و نقل می باشد . در این زمینه قابلیتهای تجزیه و تحلیل شبکه در سیستمهای اطلاعات مکانی ( GIS ) از جمله محاسبه کوتاهترین مسیرمی تواند بسیار مفید واقع شود . در این مقاله الگوریتم های کوتاهترین مسیر نظیر دیکسترا، بلمن فورد ، فلوید – وارشال و جانسون مورد نقد ، بررسی و مقایسه قرار گرفته و الگوریتم دیکسترا با توجه به قابلیتهایش برای حل مساله کوتاهترین مسیر انتخاب گشت . این الگوریتم برای داده های حجیم ( یعنی بیش از ۳۰۰۰ گره ) دارای سرعت پایینی است و نمی توان آن را برای حل کوتاه ترین مسیر در کاربردهای آنی مانند وب بکار برد . در این تحقیق روشی جدید جهت بهینه سازی الگوریتم دیکسترا ابداع گردید ونتایج بر روی شبکه راههای ایران جهت تعیین کوتاهترین مسیر بطور موفقیت آمیزی تست شد بنحوی که سرعت اجرای الگوریتم بهینه سازی شده نسبت به الگوریتم دیکسترا تا میزان ۷۵ درصد افزایش یافت

Keywords:

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