صفحه‌ها: ۱ ۲
این تست رو از طریق رد گزینه بهتر میشه حل کرد.
گزینه ۲ غلطه چون برای گراف با یال منفی و بدون دور منفی درست کار میکنه.
گزینه ۳ و ۴ هم غلطه به دلیل بالا.
فلوید فقط با دور منفی مشکل داره که منفی بینهایت تشخیص میده. شاید از همین طریق بشه وجود دور منفی رو تشخیص داد و لذا گزینه ۱ درست میشه.
سلام من اغلب پاسخها رو که مطالعه کردم دیدم اغلب دوستان چند جا به خطا رفتن و هیچکی جواب کامل و خوبی نداده تا بحث برای همیشه تموم بشه لذا این بحث رو به طور خلاصه با مقایسه جوانب مختلف سه الگوریتم جمع میکنم
نقل قول:
۱- بلمن فورد-
مشابه با دایجسترا برای یافتن کوتاهترین مسیر تک مبدا است-پیچیدگی n*e است- با یال منفی کار میکند- با دورمنفی کار نمیکند- قادر به تشخیص دور منفی است
۲- فلوید-
پویا است- برای یافتن کوتاهترین مسیر از تمام (هر) مبدا (یعنی همه زوج نقطه ها)میباشد (اولین تفاوت با بلمن فورد!!!)- پیچیدگی n به توان ۳ است (دومین تفاوت!!)- با یال منفی ممکن است جواب درست ندهد!! (منبع: مساله ۵۳/۶ کتاب ۶۰۰ مساله دکتر قدسی) (سومین تفاوت!!)- بدیهی است که با دور منفی هم کار نمیکند!!- و البته میتواند دور منفی را تشخیص دهد (مشابهت با بلمن فورد!!)
۳- دایجسترا- اساسا با دور و یال منفی مشکل دارد!
سلام من اغلب پاسخها رو که مطالعه کردم دیدم اغلب دوستان چند جا به خطا رفتن و هیچکی جواب کامل و خوبی نداده تا بحث برای همیشه تموم بشه لذا این بحث رو به طور خلاصه با مقایسه جوانب مختلف سه الگوریتم جمع میکنم
نقل قول:
۱- بلمن فورد-
مشابه با دایجسترا برای یافتن کوتاهترین مسیر تک مبدا است-پیچیدگی n*e است- با یال منفی کار میکند- با دورمنفی کار نمیکند- قادر به تشخیص دور منفی است
۲- فلوید-
پویا است- برای یافتن کوتاهترین مسیر از تمام (هر) مبدا (یعنی همه زوج نقطه ها)میباشد (اولین تفاوت با بلمن فورد!!!)- پیچیدگی n به توان ۳ است (دومین تفاوت!!)- با یال منفی ممکن است جواب درست ندهد!! (منبع: مساله ۵۳/۶ کتاب ۶۰۰ مساله دکتر قدسی) (سومین تفاوت!!)- بدیهی است که با دور منفی هم کار نمیکند!!- و البته میتواند دور منفی را تشخیص دهد (مشابهت با بلمن فورد!!)
۳- دایجسترا- اساسا با دور و یال منفی مشکل دارد!