برای یافتن کوتاه ترین مسیر‌ها از مبدا واحد به مقصد های متفاوت از الگوریتم دایجسترا استفاده میشود که از مرتبه تتای n^2هست اما ۲ پیاده سازی دیگه هم داریم:[attachment=100]
که در آن e تعداد یال هاست.
اگه گراف همبند باشه (یا تقریباً همبند) انگاه e=n^2
ولی اگر گراف خلوت باشه e=n
پس نتیجه میگیریم در بدترین حالت اگر این الگوریتم با heap پیاده سازی بشه مرتب اون: [attachment=101]
بقیه رو خودتون بررسی کنید.
زمانبندی بر مبنای کمینه کردن زمان کل ،نیاز به مرتب سازی بر اساس ترتیب صعودی زمانشان دارند پس در حالت کلی از مرتبه( teta(nlogn
تعداد درخت های پوشای گراف کامل برابر است با : (n^(n-2
در کل الگوریتم های حریصانه در تمام مسائل باسرعت بیشتری(نسبت به برنامه نویسی پویا،تقسیم و حل،عقبگرد) به جواب می رسند،نیاز به حافظه کمی دارندو بسیار کارامد هستند.تنها مسئله مهم مسئله‌ی بهینه بودن آن هاست.ممکن است جوابی که پیدا می کنند بهینه نباشد ثابت کردن بهینگی الگوریتم های حریصانه کار بسیار بسیار مشکلی است.
نکته دیگری از جزوه دکتر سید جوادی:
الگوریتم Prim دو محدودیت وجود دارد : اول آنکه در جواب بدست آمده حلقه ایجاد نشود و دوم آنکه در حین مراحل و در پایان کار ، جنگل ایجاد نشود . اگر تعداد رئوس را با n در نظر بگیریم آنگاه الگوریتم موجود معادل [tex]\Theta (n^{2})[/tex] است .
این الگوریتم دارای اصل بهینگی می باشد .
اگر گراف خلوت باشد از الگوریتم کروسکال استفاده می شود که دارای مرتبه [tex]\Theta (nlgn)[/tex] است .
اگر گراف خلوت نباشد از الگوریتم پریم استفاده می شود که دارای مرتبه [tex]\Theta (n^{2})[/tex] است .
الگوریتم کروسکال دارای اصل بهینگی می باشد .
منبع : کتاب راهیان ارشد
- در روش پریم در هر مرحله ، همبندی درخت رعایت می شود و اما در روش کراسکال در مرحله پایانی این امر رخ میدهد .
- اگر وزن یالها مجزا باشد ، حتما درخت های یکسانی را دو روش ایجاد می کنند .
- اگر وزن های یکسان داشته باشیم درخت های مختلف اما با هزینه یکسان تولید می شود .
این فایل به زیبایی ساخت درخت پوشای مینیمم توسط دو الگوریتم فوق را نمایش می دهد .
منبع :راهیان ارشد
بررسی الگوریتم solin با ذکر یک مثال:
[attachment=5532]