الگوریتم دایجسترا
این الگوریتم یکی از الگوریتمهای پیمایش گراف است که مسئله کوتاهترین مسیر از مبدأ واحد را برای گرافهای وزنداری که یال با وزن منفی ندارند، حل میکند و در نهایت با ایجاد درخت کوتاهترین مسیر، کوتاهترین مسیر از مبدأ به همه رأسهای گراف را به دست میدهد. همچنین میتوان از این الگوریتم برای پیدا کردن کوتاهترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاهترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.
روش انجام کار :
این الگوریتم چگونه کار میکند؟
در حین اجرای الگوریتم دو چیز به طور ضمنی نگهداری میشود. یکی مجموعهٔ S از رأسهایی که وزن کوتاهترین مسیر از مبدأ تا آنها مشخص شده و دیگری دنبالهٔ d که برای هر رأس v، مقدار d_v برابر وزن کوتاهترین مسیر از مبدأ تا v است به شرطی که تمام رأسهای این مسیر به جز v از رئوس داخل S باشند. S در ابتدا تهی و مقادیر d برای همهٔ رئوس به غیر از مبدأ بینهایت است و مقدار آن برای مبدأ صفر گذاشته میشود. الگوریتم در هر مرحله رأسی خارج S را که d برای آن کمترین است انتخاب و به مجموعهٔ S اضافه میکند و سپس مقادیر d را برای رئوس همسایه آن رأس بهروز مینماید. در صورتی که نیاز به تشکیل درخت کوتاهترین مسیر باشد، الگوریتم میبایست دنبالهٔ pi را که pi_v پدر رأس v در درخت کوتاهترین مسیر است، به همراه دنبالهٔ d بهروز کند.
در پیادهسازی، برای اینکه مشخص کنیم چه رئوسی در مجموعه S هستند، در هر مرحله رأس وارد شده به S را برچسب میزنیم.
در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهنده ی مسافت بین مبدا و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدا و مقصد موجود نمی باشد.بیشتر بخوانید سورس پروژه آزمون گیر هوشمند به زبان سی شارپ همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهنده ی راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود
همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهنده ی راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود
نتیجه نهایی :
پیچیدگی زمانی
در سادهترین پیادهسازی الگوریتم دایکسترا، دادهها در آرایه یا لیست پیوندی ذخیره میشوند که بدین ترتیب مینیمم مقدار d برای رئوس خارج S با الگوریتمی خطی یافت میشود. در این حالت پیچیدگی زمانی O(|V|^2+|E|) خواهد بود، چرا که در گراف بدون جهت هر یال دقیقاً دوبار و در گراف جهتدار هر یال دقیقاً یک بار پیمایش میشود و همچنین پیدا کردن مینیمم، (|O(|V زمان میخواهد که این مینیمم پیدا کردن |V| بار تکرار خواهد شد.
از جمله مهمترین کاربردهای این روش میتوان به محاسبهٔ کوتاه ترین فاصلهٔ دو نقطه در یک شهر از طریق راههای زمینی اشاره نمود. برای محاسبهٔ کوتاه ترین مسیر بین دو نقطه باید نقاط مورد نظر در یک نقشه را علامت گذاری کرد و با استفاده از مشخصات نقاط (طول، عرض و ارتفاع) فاصلهٔ دو نقطه را در هر بار عملیات محاسبه نمود. توجه داریم که در ترافیک سرعت خودروها به شدت پایین آمده و این امر میتواند در انتخاب کوتاه ترین مسیر تاثیر گذار باشد چرا که ممکن است بین دو نقطه a,b راههای ۱و۲ موجود باشد که راه ۱ اتوبان و از خارج شهر و راه ۲ از داخل شهر عبور میکند. فرض کنید فاصلهٔ a,b از طریق راه ۱ حدود ۱۰ کیلومتر و از طریق راه ۲ حدود ۷ کیلومتر باشد ولی راه ۲ علی رقم فاصلهٔ کمتر دارای ترافیک سنگین است در نتیجه میتوان انتظار داشت که در ساعات شلوغی استفاده از راه ۱ بهتر باشد. از آن جا که اساس محاسبات در این روش بر پایهٔ فاصله بین دو نقطه است میتوان کاهش سرعت را با افزایش فواصل هم ارز نمود چرا که اگر رابطهٔ سرعت و فاصله را خطی در نظر بگیریم (D=V.T)تاثیر کاهش سرعت و افزایش مسافت یکسان است. از این رو لازم است تا ضرایب تعدیلی در فواصل بین نقاط ضرب شده و این مسائل را در محاسبات لحاظ کرد. از جمله مهم ترین این ضرایب میتوان به ۳ مورد زیر اشاره نمود: ۱-ضریب ترافیک و شلوغی ۲-ضریب عرض معبر ۳-ضریب شیب که نشانگر افت سرعت در سر بالایی هااست. گرچه تعیین این ضرایب برای نقاط مختلف شهر نیازمند کارشناسان متخصص ترافیک و بررسیهای آماری دقیق میباشد ولی میتوان انتظار داشت که در اکثر موارد این ضرایب بین مقادیر ۱ تا ۲ بسته به شرایط تغییر کنند.
سورس الگوریتم دایکسترا
نشانی ایمیل شما منتشر نخواهد شد. بخشهای موردنیاز علامتگذاری شدهاند *
Current ye@r *
Leave this field empty
Copyright © 2010 Dlbook Team