سلام، شب بخیر
من یه سوال کوچیک برام بوجود اومده تو فلوید اون هم اینه که آیا میشه دور زد و بعد به یک راس رسید؟
مثلا فرض کنیم یه راس داریم که وزنش منفی هست (-۶ مثلا) بعد اگر بریم تو اون راس و برگردیم مینیمم عوض میشه و چون عدد منفی هست.
مثلا برای رسیدن به راس ۳، ابتدا از راس یک بریم به راس دو (که وزن دو به راس یک منفی هست) و بعد برگردیم به یک و سپس برسیم به راس ۳...آیا این ممکن هست؟
مرسی
اگه منظورتون خود کد الگوریتم فلوید هستش که خودش دور منفی رو تشخیص میده و ادامه نمی ده!
کلا فلوید و بلمن فورد با دور منفی کار نمی کنن!یعنی اگه دور منفی بزنید LOOP منفی میشه!!!!
اگه اشتباه می گم دوستان دیگه تصحیح کنن!
(۱۱ دى ۱۳۹۱ ۰۷:۵۳ ب.ظ)۸Operation نوشته شده توسط: اگه منظورتون خود کد الگوریتم فلوید هستش که خودش دور منفی رو تشخیص میده و ادامه نمی ده!
کلا فلوید و بلمن فورد با دور منفی کار نمی کنن!یعنی اگه دور منفی بزنید LOOP منفی میشه!!!!
اگه اشتباه می گم دوستان دیگه تصحیح کنن!
مرسی از پاسخ شما. من هم هنوز مطمئن نیستم که این درست هست یا نه اما در سوالی که استاد حل کرده، به راسی رفته که حاوی وزن منفی بوده برای همین وزن کد کمتر شده و مینیمم رو اون مسیر قرار داده ...
ببخشید من یه اشتباهی کردم!
بلمن فورد دور منفی رو تشخیص میده! نه فلوید!!!
تنها راه تشخیص دور منفی به کمک فلوید اینه که بعد از اتمام الگوریتم یه بار دیگه مسئله رو حل کنیم اگه هزینه ها کمتر شد حاکی از وجود دور منفی در گرافه!
البته نکته اصلی هم اینه که این دو با دور منفی کار نمی کنن!اما توجه کنید که با وزن منفی کار می کنن(در صورت نبود دور منفی )!