ارزيابي آلگوريتمهاي كوتاهترين مسير با تأكيد بر آلگوريتم Dijkstra و كاربردهاي آن در GIS  Fulltext 

[ روزبه شاد ] - گروه مهندسي ژئودزي و ژئوماتيك
[ حميد عبادي ] - گروه مهندسي ژئودزي و ژئوماتيك
[ عليرضا وفايي نژاد ] - گروه مهندسي ژئودزي و ژئوماتيك

خلاصه مقاله:

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

آلگوريتم كوتاهترين مسير ، GIS ، شبكه ، برچسب گذاري.