سلام همگی
اگه توی گرافی وزن با یال منفی داشته باشیم و به وزن همه یالها مقدار ثابت اضافه بکنیم که دیگه وزن منفی نداشته باشیم میتونیم از الگوریتم دایجکسترا برای حل کوتاهترین مسیر استفاده کنیم؟
پیشاپیش ممنون
(۰۴ دى ۱۳۹۳ ۰۴:۱۹ ق.ظ)shayesteNEY نوشته شده توسط: سلام همگیسلام
اگه توی گرافی وزن با یال منفی داشته باشیم و به وزن همه یالها مقدار ثابت اضافه بکنیم که دیگه وزن منفی نداشته باشیم میتونیم از الگوریتم دایجکسترا برای حل کوتاهترین مسیر استفاده کنیم؟
پیشاپیش ممنون
فکر نمی کنم این کار عملی باشه چون مثلا ممکنه یه مسیر تعداد یالاش خیلی زیاد باشه اما یال هاش کم هزینه باشن و به این صورت کوتاه ترین مسیر باشه تو گراف اولیه . اما با مثبت کردن چون این به همه یالاش یه مقداری اضافه شده و از طرفی همانطور که گفتم کلی یال داره احتمالا دیگه کوتاهترین مسیر نیست و یه مسیر دیگه ای که احتمالا مسیر با تعداد یال کمتری هست کوتاه ترین مسیر خواهد بود.اگر توضیح کافی نیست بفرمایید
متشکرم بابت توضیحاتتون
متوجه شدم
یه سوال دیگه همین جا بپرسم من متوجه تفاوت دور منفی با یال منفی نمیشم
حلقه داشتن = دور منفی؟
با سلام دوست عزیز دور منفی یعنی یه حلقه ای باشه که وقتی وزن یال های حلقه را جمع کنیم حاصل یک عدد منفی بشه
فرض کنید یه حلقه داریم با دو تا یال یکیش -۸ یکیش ۵
خوب جمع اینها میشه -۳ پس میگیم یه حلقه منفی داره
موفق باشید