سلام دوستان عزیز من دوتا سئوال درسی داشتم در مورد الگوریتم دیکسترا اگه واقعا میتونید کمک کنید پایان ترم باید تمرینات رو تحویل بدم با تشکر.
.
.
۱/الگوریتم دیکسترا را طوری اصلاح کنید که ببیند ایا گراف جهت دار, چرخه دارد یا خیر.الگوریتم خود را تحلیل کرده نتایج را با استفاده از نماد مرتبه نشان دهید؟
.
.
۲/ایا الگوریتم دیکسترا را می توان برای یافتن کوتاه ترین مسیر در گرافی با وزن های منفی به کار گرفت؟ برای پاسخ خود دلیل بیاورید.
برای سوال اول٬ فکر میکنم میشه اینطور گفت که:
ما در الگوریتم دیکسترا٬ یک مجموعه‌ی یال‌های گزیده شده داریم و مجموعه‌ی گره‌هایی که دیده نشدند.
زمانیکه در این الگوریتم Extract_Min رو انجام می‌دیم٬ (فکر میکنم) پیش از اون٬ باید بررسی کنیم که آیا اجتماع یال جدید با مجموعه‌ی قبلی٬ دارای چرخه هست یا خیر. بنابراین باید یک بررسی بین همه‌ی یال‌هایی که انتخاب شدند٬ داشته باشیم. درباره‌ی پیچیدگی زمانی اون میشه بحث کرد.
۲. خیر! چون این الگوریتم یک الگوریتم حریصانه هست٬ در هر مرحله٬ کورکورانه کم‌ترین هزینه رو انتخاب می‌کنه و کاری به یال‌های بعدی نداره. فرضاً اگر مسیری از یک گره تا گره‌ی دیگه با وجود یال منفی (با واسط گره‌ی دیگری) وجود داشته باشه٬ این الگوریتم٬ الزاماً راه حل بهینه رو پیدا نمی‌کنه. (الزاماً پیدا نمی‌کنه٬ ممکنه پیدا کنه ولی روی این موارد٬ ضعیف هست.)
(۱۲ دى ۱۳۹۰ ۱۰:۵۳ ب.ظ)mam نوشته شده توسط: برای سوال اول٬ فکر میکنم میشه اینطور گفت که:از بابت جواب سئوال دو دست شما درد نکنه تقریبا به دردم خورد
ما در الگوریتم دیکسترا٬ یک مجموعه‌ی یال‌های گزیده شده داریم و مجموعه‌ی گره‌هایی که دیده نشدند.
زمانیکه در این الگوریتم Extract_Min رو انجام می‌دیم٬ (فکر میکنم) پیش از اون٬ باید بررسی کنیم که آیا اجتماع یال جدید با مجموعه‌ی قبلی٬ دارای چرخه هست یا خیر. بنابراین باید یک بررسی بین همه‌ی یال‌هایی که انتخاب شدند٬ داشته باشیم. درباره‌ی پیچیدگی زمانی اون میشه بحث کرد.
در مورد سئوال اول میتونید الگوریتم اصلاح شده اش رو بنویسید؟