سورس پروژه الگوریتم دایجسترا
نوشته شده توسط projejob در تاریخ ۱۳۹۲/۰۳/۰۳ | مرتبط با : سورس های برنامه نویسی, پروژه های سی پلاس پلاس | 1,232 views

سورس پروژه الگوریتم دایجسترا به زبان سی پلاس پلاس

 

Dijksta_Anim

 

سورس پروژه دایجسترا رو به زبان سی پلاس پلاس به درخواست چندی از دوستان اماده دانلود کرده ایم که امید وارم مفید باشه استفاده لازم رو ببرید.پروژه به همراه سورس کامل منتشر شده است در ادامه توضیحاتی در مورده این الگوریتم میدم که دوستان هم با روش کار این الگوریتم اشنا بشن پس تا ادامه با ما باشید…

این الگوریتم که عنوانش را از ابداع کننده آن یعنی دیکسترا هلندی گرفته است کوتاهترین مسیر در یک گراف همبند ، جهت دار و وزن دار با وزن غیر منفی را بدست می آورد .

بطور مثال اگر تعدادی شهر را به وسیله یک گراف نشان دهیم و فاصله بین شهرها را بوسیله یالهای گراف نشان دهیم بطوریکه می دانیم فاصله بین دو شهر یک عدد مثبت است آنگاه می توان با استفاده از الگوریتم دیکسترا کوتاهترین مسیر بین دو شهر را بدست آورد .

 

 

این الگوریتم کوتاهترین فاصله بین مبدا با سایر شهرها را بدست می آورد و نمی تواند کوتاهترین فاصله بین هر دو نقطه دلخواه را بدست آورد(مگر آنکه بر روی همه مسیرها آن را اعمال کنیم) و یا نمی تواند گراف با یالهای دارای وزن منفی را پردازش کند برای این منظور باید از الگوریتم هایی نظیر فلوید- وارشال و بلمن- فورد استفاده نمایید

شبه کد الگوریتم دیکسترا در زیر ارائه شده است
DIJKSTRA(G , W , S)
Initialize single-source ( G , S )
S={ }
Q=V[G]
While Q <> { } do
U = Extract-Min Q
S = S + {u}
For each vertex V member of ADJ[u] do
Relax (u , v , w)

توضیح بیشتر
در این الگوریتم دو مجموعه S,Q وجود دارد . مجموعه S شامل همه رئوس است این مجموعه برای آن است که ما به مقادیر ADJ[u] که همان هزینه کوتاهترین مسیر است نیاز داریم . مجموعه Q نیز شامل همه رئوس است .
مجموعه S در ابتدا تهی می باشد و در هر گام یک عضو (راس) از مجموعه Q به مجموعه S انتقال می یابد ، این راس انتقال یافته در واقع همان راسی است که فاصله تا آن راس ، کمترین مقدار می باشد .

مرتبه اجرایی الگوریتم دیکسترا
این الگوریتم در پیاده سازی و بدست آوردن زمان مصرفی می تواند ساختار متفاوتی از خود نشان دهد اما اگر در پیاده سازی این الگوریتم از ساختارماتریس اسپارس و هرم-دوجمله ای (binary heap) استفاده نماییم و برای نگهداری مسیر از صف (Queue) بهره ببریم آنگاه زمان مصرفی این الگوریتم به حداقل مقدار خود یعنی (|O( ( |V| + |E| )* Log|V خواهد رسید . توجه شود اگر ساختار پیاده سازی از ماتریس اسپارس و هرم – دوجمله ای مینیمم استفاده نکند مرتبه زمانی به مقدار (O(V^2 + E) = O(V^2 خواهد رسید .
برگرفته از مقاله م.جم پور CIS2006 با تلخیص

 

 

 

لینک دانلود فقط برای اعضای سایت قابل مشاهده می باشد برای عضویت کلیک کنید .

 

 


پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

*

HTML tags are not allowed.


Copyright 2010 - All right reserved By Projejob.ir Team
تمامی حقوق مطالب و تصاویر محفوظ است، نقل و استفاده از آنها در سایت ها و نشریات تنها با ذکر منبع مجاز میباشد

webmasters forum
دانلود سورس