ورود / ثبت نام
0
0

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

رایگان!

بعد از عضویت رایگان دانلود کنید.

عضویت در سایت

دایجسترا

دایجسترا

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

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

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

شبه کد الگوریتم دایجسترا در زیر ارائه شده است
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 خواهد رسید .

منبع مقاله :برنامه نویس

اطلاعات بیشتر

زبان پروژه

C

نقد و بررسی‌ها

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

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

هیچ دیدگاهی برای این محصول نوشته نشده است.