سلام .

(۱۴ دى ۱۳۹۱ ۰۴:۴۷ ب.ظ)Amir V نوشته شده توسط:  آیا فلوید با دور منفی کار میکنه؟

طبق اثباتی که توی کتاب CLRS آورده شده اگه دور منفی در گراف وجود داشته باشه اونوقت کوتاه ترین مسیر بین دو راس $-\infty$ میشه پس فلوید نمیتونه با دور منفی کار کنه .
دو تا نکته قابل اثبات در همین بحث وجود داره که بهتره حواسمون بهش باشه البته به راحتی هم قابل اثبات هستن :
۱/ با الگوریتم فلوید میتوان وجود دور منفی در گراف را تشخیص داد
۲/ الگوریتم فلوید میتواند با وجود یال منفی(نه دور منفی) کوتاه ترین مسیر بین دو راس رو پیدا کند

(۱۴ دى ۱۳۹۱ ۰۴:۴۷ ب.ظ)Amir V نوشته شده توسط:  ۱/آیا فلوید برای گراف جهت دار و بی جهت یکسانه؟
۲/آیا بهینگی برای هر دو برقراره؟(تست IT سراسری ٨٤) ||||| آیا از فلوید برای طولانی ترین مسیر میشه استفاده کرد؟

۱/من تا حالا گراف بدون جهت در صورت تست فلوید ندیدم . ولی جهت دار بودن یا نبودن گراف برای الگوریتم فلوید مهم نیست چون به نظر من مهم فقط وزن یال هاست مثلا میتونیم وجود یک یال بدون جهت بین دو راس رو همون یال دو جهته در نظر بگیریم . در کل میگم من ندیدم گراف بدون جهت رو واسه فلوید بدن اگه تو دیدی بزار تا روش بحث کنیم .

۲/ این تست IT84 ، میخواد تعداد گام طولانی ترین مسیر رو بین دو راس در یک گراف بدون وزن پیدا کنه پس معلومه که در این مورد اصلا الگوریتم فلوید به درد نمیخوره چون این الگوریتم با وزن یال های کار میکنه و کوتاه ترین مسیر وزنی رو پیدا میکنه نه بر اساس طول مسیر. پس در حیطه ی الگوریتم های پویا نمیگنجه چون نمیتونیم مسیر بهینه رو پیدا کنیم و در مورد این تست باید به دیگر الگوریتم ها مثل BFS و امثالهم رجوع کرد

(۱۴ دى ۱۳۹۱ ۰۵:۵۵ ب.ظ)mp1368 نوشته شده توسط:  بلمن فورد بر عکس فلوید میتونه با وجود دور منفی باز کوتاه ترین مسیر رو بین دو راس پیدا کنه بقیه موارد هم که دیگه تابلو هستش.

مطمئنید در مورد این حرفتون؟! به نظر من نمی تونه!هیچ کدوم با دور منفی نمی تونن!

بچه ها ممنون میشم بحث رو یه جمع بندی کلی بکنیم!

هر دو الگوریتم می تونن وجود دور منفی رو در گراف تشخیص بدن.

الگوریتم بلمن فورد بر عکس فلوید در صورت وجود سیکل منفی باز هم می تونه بدون هیچ مشکلی کوتاهترین مسیر رو تشخیص بده اما فلوید در صورت وجود سیکل منفی نمیتونه کوتاهترین مسیر رو برگردونه و فقط سیکل منفی رو تشخیص میده! درسته؟؟!

و تفاوت دیگه هم مرتبه اجرایی دو تا الگوریتمه دیگه همین؟

---

یه سوال دیگه هم داشتم ممنون میشم جواب بدید.
وقتی گراف شلوغ باشه و دور منفی نداشته باشیم از بین الگوریتم های فلوید و بلمن فورد بهترین و بدترین انتخاب برای پیدا کردن کوتاهترین مسیر کدومه؟
(برای هیپ از باینری هیپ استفاده شده)

سوال آزمون آزمایشی بود.
پاسخ رو فلوید-بلمن فورد انتخاب کرده، میشه دلیلشو یکی بگه؟
ممون. موفق باشید دوستای خوبم.

(۱۹ دى ۱۳۹۱ ۰۲:۴۳ ب.ظ)Eng_Sara نوشته شده توسط:  هر دو الگوریتم می تونن وجود دور منفی رو در گراف تشخیص بدن.

الگوریتم بلمن فورد بر عکس فلوید در صورت وجود سیکل منفی باز هم می تونه بدون هیچ مشکلی کوتاهترین مسیر رو تشخیص بده اما فلوید در صورت وجود سیکل منفی نمیتونه کوتاهترین مسیر رو برگردونه و فقط سیکل منفی رو تشخیص میده! درسته؟؟!

ببین دو تاشون سیکل منفی رو تشخیص میدن. اما هیچ کدوم مسئله رو حل نمیکنن. توی الگوریتمی که عکسش رو گذاشتم میبینی که نوشته اررور بر میگردونه.

نقل قول: و تفاوت دیگه هم مرتبه اجرایی دو تا الگوریتمه دیگه همین؟

آره.

نقل قول: یه سوال دیگه هم داشتم ممنون میشم جواب بدید.

نمیدونم...

(۱۹ دى ۱۳۹۱ ۰۲:۴۳ ب.ظ)Eng_Sara نوشته شده توسط:  بچه ها ممنون میشم بحث رو یه جمع بندی کلی بکنیم!

هر دو الگوریتم می تونن وجود دور منفی رو در گراف تشخیص بدن.

الگوریتم بلمن فورد بر عکس فلوید در صورت وجود سیکل منفی باز هم می تونه بدون هیچ مشکلی کوتاهترین مسیر رو تشخیص بده اما فلوید در صورت وجود سیکل منفی نمیتونه کوتاهترین مسیر رو برگردونه و فقط سیکل منفی رو تشخیص میده! درسته؟؟!

و تفاوت دیگه هم مرتبه اجرایی دو تا الگوریتمه دیگه همین؟

---

یه سوال دیگه هم داشتم ممنون میشم جواب بدید.
وقتی گراف شلوغ باشه و دور منفی نداشته باشیم از بین الگوریتم های فلوید و بلمن فورد بهترین و بدترین انتخاب برای پیدا کردن کوتاهترین مسیر کدومه؟
(برای هیپ از باینری هیپ استفاده شده)

سوال آزمون آزمایشی بود.
پاسخ رو فلوید-بلمن فورد انتخاب کرده، میشه دلیلشو یکی بگه؟
ممون. موفق باشید دوستای خوبم.

سلام
اون همه زحمت کشیده شده برای پاسخ نامه توش کامل توضیح دادبه شده من نمیفهمم چرا هنوز ابهام وجود داره:پی
الگوریتم فلوید یک الگوریتم برنامه نویسی پویا می باشد که مرتبه آن V به توان ۳ می باشد. الگوریتم فلوید تمام کوتاه ترین مسیرها را به تمام راس ها گیر می آورد.
از طرفی دیگر مرتبه الگوریتم بلمن فورد برابر با O(VE) می باشد. که در گراف شلوغ به دلیل این که یالها از مرتبه V به توان ۲ می باشند بنابراین مرتبه اش می شود V به توان ۳/ اما الگوریتم بلمن فورد برای یافتن کوتاه ترین مسیرها از یک راس به باقی راس ها میباشد. درحالیکه تو صورت سوال کوتاه ترین مسیر بین هر دو جفت راس را خواسته است. بنابراین باید بر روی تمامی V راس آن را اجرا کنیم که مرتبه اش می شود از مرتبه V به توان ۴/
اینجا امکانات تایپیش محدوده نتونستم فرمولها رو درست تایپ کنم شرمنده

سلام من اغلب پاسخها رو که مطالعه کردم دیدم اغلب دوستان چند جا به خطا رفتن و هیچکی جواب کامل و خوبی نداده تا بحث برای همیشه تموم بشه لذا این بحث رو به طور خلاصه با مقایسه جوانب مختلف سه الگوریتم جمع میکنم

نقل قول:

۱- بلمن فورد-

مشابه با دایجسترا برای یافتن کوتاهترین مسیر تک مبدا است-پیچیدگی n*e است- با یال منفی کار میکند- با دورمنفی کار نمیکند- قادر به تشخیص دور منفی است

۲- فلوید-

پویا است- برای یافتن کوتاهترین مسیر از تمام (هر) مبدا (یعنی همه زوج نقطه ها)میباشد (اولین تفاوت با بلمن فورد!!!)- پیچیدگی n به توان ۳ است (دومین تفاوت!!)- با یال منفی ممکن است جواب درست ندهد!! (منبع: مساله ۵۳/۶ کتاب ۶۰۰ مساله دکتر قدسی) (سومین تفاوت!!)- بدیهی است که با دور منفی هم کار نمیکند!!- و البته میتواند دور منفی را تشخیص دهد (مشابهت با بلمن فورد!!)

۳- دایجسترا- اساسا با دور و یال منفی مشکل دارد!

---

سلام من اغلب پاسخها رو که مطالعه کردم دیدم اغلب دوستان چند جا به خطا رفتن و هیچکی جواب کامل و خوبی نداده تا بحث برای همیشه تموم بشه لذا این بحث رو به طور خلاصه با مقایسه جوانب مختلف سه الگوریتم جمع میکنم

نقل قول:

۱- بلمن فورد-

مشابه با دایجسترا برای یافتن کوتاهترین مسیر تک مبدا است-پیچیدگی n*e است- با یال منفی کار میکند- با دورمنفی کار نمیکند- قادر به تشخیص دور منفی است

۲- فلوید-

پویا است- برای یافتن کوتاهترین مسیر از تمام (هر) مبدا (یعنی همه زوج نقطه ها)میباشد (اولین تفاوت با بلمن فورد!!!)- پیچیدگی n به توان ۳ است (دومین تفاوت!!)- با یال منفی ممکن است جواب درست ندهد!! (منبع: مساله ۵۳/۶ کتاب ۶۰۰ مساله دکتر قدسی) (سومین تفاوت!!)- بدیهی است که با دور منفی هم کار نمیکند!!- و البته میتواند دور منفی را تشخیص دهد (مشابهت با بلمن فورد!!)

۳- دایجسترا- اساسا با دور و یال منفی مشکل دارد!

ممنون واسه جواب.

میشه همین مسئله رو برای بلمن فورد هم بگید؟

(۱۴ دى ۱۳۹۱ ۰۵:۵۲ ب.ظ)Amir V نوشته شده توسط:  ممنون واسه جواب.
میشه همین مسئله رو برای بلمن فورد هم بگید؟

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

اره منم موافقم.

بلمن فورد میتونه دور منفی رو تشخیص بده! اما نمیتونه در این شرایط مسیر مینیموم رو پیدا کنه و ارور میده.

اینو الان تو پوران دیدم:


اما فلوید رو فکر کنم درست گفتن. نمیدونم...

Sent from my Google Galaxy Nexus using Tapatalk 2.4

(۱۴ دى ۱۳۹۱ ۰۸:۴۶ ب.ظ)Amir V نوشته شده توسط:  اره منم موافقم.

بلمن فورد میتونه دور منفی رو تشخیص بده! اما نمیتونه در این شرایط مسیر مینیموم رو پیدا کنه و ارور میده.

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

پس با این تفاسیر هیچ الگوریتمی دور منفی (نه یال منفی) را نمی تواند حل کند؟

(۱۴ دى ۱۳۹۱ ۰۵:۳۴ ب.ظ)mp1368 نوشته شده توسط:  ۲/ الگوریتم فلوید میتواند با وجود یال منفی(نه دور منفی) کوتاه ترین مسیر بین دو راس رو پیدا کند

مطمئنید؟ الان من یه تست تو مقسمی دیدم این جمله رو نقض می کرد صورت تست:
اگه یالهای منفی داشته باشیم کدوم گزینه بهترین توصیف برای فلویده؟(مهندسی ۸۴)
۱- می شه باهاش وجود یا عدم وجود دور منفی رو تشخیص داد
۲- الگوریتم برای یالهای منفی ولی بدون دور منفی ممکن است در دور بیفتد.
۳- الگوریتم برای یالهای منفی ولی بدون دور منفی متوقف می شود ولی درست کار نمی کند.
۴- الگوریتم برای یالهای منفی ولی بدون دور منفی متوقف می شود ولی جوابش همیشه غلطه!

جواب:۱


توضیح بدین ممنون می شم

این تست رو از طریق رد گزینه بهتر میشه حل کرد.
گزینه ۲ غلطه چون برای گراف با یال منفی و بدون دور منفی درست کار میکنه.
گزینه ۳ و ۴ هم غلطه به دلیل بالا.

فلوید فقط با دور منفی مشکل داره که منفی بینهایت تشخیص میده. شاید از همین طریق بشه وجود دور منفی رو تشخیص داد و لذا گزینه ۱ درست میشه.

پس تفاوت بلمن فورد و فلوید چیه؟

جز اینکه فلوید از مرتبه $O(n^3)$ و بلمن-فورد از $O(n.e)$ هست، دیگه چه فرقی دارن؟

(۱۴ دى ۱۳۹۱ ۰۹:۳۹ ب.ظ)Amir V نوشته شده توسط:  پس تفاوت بلمن فورد و فلوید چیه؟

جز اینکه فلوید از مرتبه $O(n^3)$ و بلمن-فورد از $O(n.e)$ هست، دیگه چه فرقی دارن؟

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

من چرا تو تایپیکای درسی دکمه لایک ندارم؟!

امیر ممنونم.
ولی فکر کنم تفاوت دیگه ای هم داشته باشناااااا....

________________________________________________

آقای جهانی ممنونم از توضیحاتتون.بله پاسخنامه جواب سوال رو کامل نوشته ولی کلاً من تو این دوتا الگوریتم فکر میکردم یکم لنگ میزنم!
اونم که حل شد فکر کنم!