# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  درباره الگوریتم دیکسترا (دایجسترا)

## raha_hakhamanesh

*درباره الگوریتم دیکسترا(دایجسترا)*

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

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


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

----------


## raha_hakhamanesh

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

1- استفاده در الگوریتم مسیریابی روترها و سوئیچ ها
2- . . .

----------


## mina taheri

در مورد الگوریتم بلمن فورد توضیح دهید

----------


## elnaz.r

سلام میشه لطف کنید و بگید مقالات آقای م.جم پور را از کدام سایت میتوانم بگیرم به طور کامل.مرسی

----------


## AmirhossenFekri

الگوریتم دیکسترا 
مسالهٔ      یافتن کوتاه‌ترین مسیر بین دو رأس، از مبدأ واحد و به مقصد واحد را حل می‌کند .

  دوستان اگه میشه یه منبع برای این جور الگوریتم ها معرفی کنید فرقی هم نمیکنه (انگلیسی ، فارسی) . 

میخوام تو پروژه مدیریت بحران استفاده کنم . ممنون از همه

----------


## hashemt4

سلام

آقای مهدی جم پور سال 86 استاد درس طراحی وب من بود.
آدرس وب سایت جناب جم پور: www.jampour.ir

----------

