خوب من یک مثال فرستادم . طبق اون پیش میریم .
ما توی این الگوریتم یک راس رو در نظر میگیریم و از اون به سایر رئوس الگوریتم رو پیاده سازی میکنیم که اینجا a رو گرفته .
مرحله اول گره هایی که بدون واسطه به گره a وصل شدن رو پیدا میکنیم و مینویسیم و برای بقیه مقدار بی نهایت میزاریم .
که اینجا c رو میبینه با ۴ تا و b رو میبینه با ۱ . بقیه هم که بی نهایت
مرحله ۲ : میایم از بین گره هایی که ملاقات شدن بهینه رو انتخاب میکنیم . یعنی گره b
تو مرحله ۲ حالا راس b به عنوان واسط اضافه شد . یعنی این جمله (( گره a گره .... را میبیند , به واسطه ی گره B ))
حالا میبینیم این بار به واسطه b گره d و e رو میبینه . d رو با ۸ تا و e رو با ۶ تا . گره a گره c رو هم به واسطه b میبینه و هزینش میشه ۳ . میبینیم که بهینه تر از مرجله یک بود که بطور مسنقیم میدید و ۴ بود . پس ۳ جایگزین ۴ میشه .
جالا مرجله ۳ : مینیمم اون گره هایی که ملاقات شده رو انتخاب میکنیم . ( b انتخاب شده تو مرحله قبل )
میشه گره c .
حالا تو مرحله سوم این جمله که (( گره a گره .... را میبیند بواسطه ی (b,c) یا c یا b ))
که اینجا میبینیم گره a گره e رو میبینه از طریق مسیر a به b , bبه c و c به e . درست . میبینیم هزینش میشه ۴ و بهتر از ۶ قبلی هست . پس ۴ جایگزین ۶ میشه .
حالا دوباره مینیمم این جدول انتخاب میشه که گره e هستش .
مرجه ۴ . این جمله (( گره a گره ...... را با واسطه (a,b,c,e) یا a یا b یا c یا e یا ترکیب دوتای اینها یا ۳ تایی اینها میبیند .
حالا میبینیم که a گره d رو از طریق a به b , b به c , c به e , e به d میبینه که هزینش کلا میشه ۷ تا . بهتر از ۸ تا هستش پس ۷ جایگزین ۸ میشه . و همچنین گره f رو میبینه با a به b , b به c , c به e و e به f با ۱۰ تا
این شد دیکسترا
البته به f شونصد تا مسیر داریم ( خصوصاً همه گره ها واسط میتونن باشن . ولی از بین اونا بهینه ترین از نظر هزینه رو پیدا میکنیم . چون اینجا دیگه محدودیت واسط نداریم که از فلان مسیر نشه رفت )

کسی نحوه کارشو می دونه؟

اینطوری خیلی سخته
یه راه آسونتر نداره؟
اما فکر کنم توی سوالش میگه از گره a مثلا تا گره فلان با حداقل هزینه برید نه همه گره ها.
منظورم برای سوال پایانی درس دوره کارشناسی هست.
اگه برای همه گره ها بخواد که خیلی سخت میشه.

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

(۲۸ دى ۱۳۹۳ ۰۹:۲۹ ب.ظ)ardaaalan نوشته شده توسط:  تا اونجایی که من دیدم ۴ تا جدول میدن میگن کدوم یکی بهینه الگوریتم دایجسترا برای گراف زیر است .
با ۲ بار تمرین راحت میشه
نه راه حل دیگه ای نداری
حداقل تا اونجایی که من میدونم و تو کتاب طورانی نوشته

کجای کتاب آقای طورانی در مورد دایجسترا توضیح داده ؟؟؟!!!
چرا من ندیدم :O
کدوم کتاب؟ کدوم صفحه؟



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

[quolte='L3ic' pid='327910' dateline='1421609138']

(۲۸ دى ۱۳۹۳ ۰۹:۲۹ ب.ظ)ardaaalan نوشته شده توسط:  تا اونجایی که من دیدم ۴ تا جدول میدن میگن کدوم یکی بهینه الگوریتم دایجسترا برای گراف زیر است .
با ۲ بار تمرین راحت میشه
نه راه حل دیگه ای نداری
حداقل تا اونجایی که من میدونم و تو کتاب طورانی نوشته

کجای کتاب آقای طورانی در مورد دایجسترا توضیح داده ؟؟؟!!!
چرا من ندیدم :O
کدوم کتاب؟ کدوم صفحه؟



--------------------------------------------------------------------
در مورد این الگوریتم بنظرم مرتبه زمانی و شرایط استفاده اش رو یاد بگیری کفایت میکنه
وگرنه اگر گراف بدند که با چشم هم میشه کوتاه ترین مسیر رو پیدا کرد
والبته تست هایی هم دیدم که ماتریس ایجاد شده نهاییش رو دادند و ازش یه سوال درآوردند که فقط بدونی داستانش چیه حله
[/quote]

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