ارزیابی آلگوریتمهای کوتاهترین مسیر با تأکید بر آلگوریتم Dijkstra و کاربردهای آن در GIS

یکی از مواردی که یک GIS را از سیستمهای اطلاعاتی دیگر متمایز می کند ، وجود توابع تجزیه و تحلیل مکانی در آن می باشد معمو ً لا این توابع تجزیه و تحلیل باعث ا رائه ب هترین گزینه ها و راه حلها به کار بر ان GIS می شوند . همزمان با توسعة تکنیکهای GIS توابع تجزیه و تحلیل قابل اجرا توسط GIS نیز به طور قابل توجهی گسترش یافته اند ، که از جمله این توابع می توان به آنالیز شبکه اشاره نمود. یکی از آنالیزهای شبکه ، یافتن کوتاهترین م سیر می باشد که به عنوان یکی از کاربردهای مهم در مسائل حمل و نقل مطرح می شود با توجه به تحقیقات و مطالعات به عمل آمده توسط محققانی همچون Noon ، Zhan و Cherkassky سه آلگوریتم ذیل در میان آلگوریتمهای مختلف مسیر یابی سریعتر اجرا می شوند و نتایج قابل اطمینان و معتبری را ارائه می دهند. این سه آلگوریتم عبارتند از :آلگوریتم Graph growth که بوسیلة دو ردیف (Queue) اجرا می شود، آلگوریتم Dijkstra که بوسیلة باکتهای تقریبی (Approximate buckets) اجرا می شود و آلگوریتم Dijkstra که بوسیلة باکتهای دوتایی (Double buckets) اجرا می شود در این راستا ، مقالة فوق ضمن بررسی اجمالی پارامترهای مؤثر بر کارائی یک آلگوریتم مسیریابی و نحوة عملکرد آلگوریتم Dijkstra سه آلگوریتم مذکور را به عنوان سریعترین آلگوریتمهای مسیر یابی مورد ارزیابی قرار داده و برای استفاده در GIS پی شنهاد می کند.

کلیدواژه ها:

آلگوریتم کوتاهترین مسیر ، GIS ، شبکه ، برچسب گذاری