(۱۹ دى ۱۳۹۲ ۰۷:۲۲ ب.ظ)masoud67 نوشته شده توسط:  سلام در کتاب الگوریتم پوران نوشته برای گراف غیرجهت دار با یال منفی ، الگوریتم فلوید لزوما جواب صحیح نمیدهد.
آیا این جمله درسته؟
تو انجمن گشتم همه گفتند که فلوید در گراف بیجهت و جهتدار کار میکنه ولی هنوز شک دارم. مخصوصا وقتی تو ویکی پدیا یه جمله دیدم که ظاهرا گفته یال منفی دور منفی ایجاد میکنه!!!!!!!! (اگه اشتباه ترجمه نکرده باشم )

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


Obviously, in an undirected graph a negative edge creates a negative cycle

یه سوال دیگه فلوید با فلوید وارشال فرق داره؟

سلام
فلوید در گراف جهتدار و بدون جهت با یال منفی کار میکنه به شرطی ک یال منفی سیکل منفی ایجاد نکنه...یعنی با یال منفی کار میکنه اما با سیکل منفی کار نمیکنه فقط وجود سیکل منفی رو با یه پیام خطا اعلام میکنه
موفق باشید

آزمون جامع مدرسان چنین جمله ای نوشته
الگوریتم فلوید با یال منفی (بدون دور منفی) در گراف جهت دار همواره جواب درست برمیگرداند ولی در گراف های غیرجهتدار ممکن است جواب درست برنگرداند

(۲۰ دى ۱۳۹۲ ۰۱:۱۴ ق.ظ)M@A نوشته شده توسط:  فلوید در گراف جهتدار و بدون جهت با یال منفی کار میکنه به شرطی ک یال منفی سیکل منفی ایجاد نکنه...

(۲۶ دى ۱۳۹۲ ۰۹:۲۷ ب.ظ)masoud67 نوشته شده توسط:  الگوریتم فلوید با یال منفی (بدون دور منفی) در گراف جهت دار همواره جواب درست برمیگرداند ولی در گراف های غیرجهتدار ممکن است جواب درست برنگرداند

آخرش فلوید در گراف جهت دار درست کار می کنه یا نادرست ؟؟

(۳۰ دى ۱۳۹۲ ۰۷:۱۸ ب.ظ)tayebe68 نوشته شده توسط:  آخرش فلوید در گراف جهت دار درست کار می کنه یا نادرست ؟؟

متاسفانه ظاهرا درست کار نمیکنه.

توی پوران به عنوان یه نکته مهم نوشته
توی آزمون جامع مدرسان هم گفته
توی اون لینک ویکی پدیا هم اینو گفته

ولی هنوز تو هیچ منبع معتبری ندیدم که تکذیب کنه . فقط توی مانشت بچه ها گفتن کار میکنه ولی از روی منبعی نگفتند. یا فقط گفتند در گراف جهتدار و بی جهت کار میکنه در گراف با یال منفی کار میکنه ولی هر دو را با هم (که در گراف غیرجهتدار با یال منفی) نگفتند
پس من فعلا احتمال را بر این میذارم که فلوید در گراف غیرجهتدار با یال منفی درست کار نمیکند