تالار گفتمان مانشت

با سلام
لطفا مدیر محترم ارجاعم ندن به این تاپیک :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

چون جوابمو اونجا نگرفتم، در واقع تیتر تاپیک شباهتی به پاسخها نداشت.
دوستان ممنون میشم یه مقایسه کلی داشته باشن.
من به دنبال یافتن تفاوت این دو الگوریتم سرچ کردم این جواب رو جایی پیدا کردم که البته قانع کننده نبود برام!
"الگوریتم فلوید وارشال برای گراف با یال منفی است و وجود یال منفی را تشخیص می دهد ولی اگر دارای دور منفی باشد آنگاه آن را تشخیص می دهد اما گزارش نمی کند .
الگوریتم بلمن-فورد گراف با یال منفی را می پذیرد و چنانچه در گراف دچار دور منفی شویم آن را گزارش می دهد."

دقت کنیدبه این نکته که :
الگوریتم فلوید - وارشال برای پیدا کردن یک مسیر بهینه در گراف جهتدار هست.(کوتاهترین مسیر)-----> تو برنامه نویسی پویا این الگوریتم رو داشتیم.
ولی الگوریتم بلمن فورد برای پیدا کردن یک درخت پوشای مینیمم در یک گراف است.

(13 آذر 1393 06:24 ب.ظ)zahra.s نوشته شده توسط: [ -> ]دقت کنیدبه این نکته که :
الگوریتم فلوید - وارشال برای پیدا کردن یک مسیر بهینه در گراف جهتدار هست.(کوتاهترین مسیر)-----> تو برنامه نویسی پویا این الگوریتم رو داشتیم.
ولی الگوریتم بلمن فورد برای پیدا کردن یک درخت پوشای مینیمم در یک گراف است.

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

(13 آذر 1393 07:44 ب.ظ)ldns0098 نوشته شده توسط: [ -> ]

(13 آذر 1393 06:24 ب.ظ)zahra.s نوشته شده توسط: [ -> ]دقت کنیدبه این نکته که :
الگوریتم فلوید - وارشال برای پیدا کردن یک مسیر بهینه در گراف جهتدار هست.(کوتاهترین مسیر)-----> تو برنامه نویسی پویا این الگوریتم رو داشتیم.
ولی الگوریتم بلمن فورد برای پیدا کردن یک درخت پوشای مینیمم در یک گراف است.

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

حرف شما صحیح ولی من جایی خوندم الگوریتم فلوید برای یافتن درخت پوشا و فلوید -وارشال برای مسیر بهینه هست!

(13 آذر 1393 07:53 ب.ظ)zahra.s نوشته شده توسط: [ -> ]من جایی خوندم الگوریتم فلوید برای یافتن درخت پوشا و فلوید -وارشال برای مسیر بهینه هست!

بعید میدونم درست باشه. کدوم کتاب بوده؟

(13 آذر 1393 01:15 ب.ظ)ldns0098 نوشته شده توسط: [ -> ]با سلام
لطفا مدیر محترم ارجاعم ندن به این تاپیک :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

چون جوابمو اونجا نگرفتم، در واقع تیتر تاپیک شباهتی به پاسخها نداشت.
دوستان ممنون میشم یه مقایسه کلی داشته باشن.
من به دنبال یافتن تفاوت این دو الگوریتم سرچ کردم این جواب رو جایی پیدا کردم که البته قانع کننده نبود برام!
"الگوریتم فلوید وارشال برای گراف با یال منفی است و وجود یال منفی را تشخیص می دهد ولی اگر دارای دور منفی باشد آنگاه آن را تشخیص می دهد اما گزارش نمی کند .
الگوریتم بلمن-فورد گراف با یال منفی را می پذیرد و چنانچه در گراف دچار دور منفی شویم آن را گزارش می دهد."

الگوریتم فلوید واسه یافتن تمام کوتاه ترین مسیرها بکار میره(کوتاه ترین مسیر بین هر دو راس مشخص) و یک الگوریتم پویا می باشد.
این الگوریتم ماتریس های A1 تا An رو مرحله به مرحله میسازه و در مرحله K فقط رئوس 1 تا K رو به عنوان رئوس میان بین هر دو راس در نظر میگیرد و به این سوال جواب میدهد که آیا راس kام رو بعنوان راس میانی در نظر بگیریم یا نه. اگر با وجود راس kام مسیر کوتاهتر شود آن را در نظر میگیرد در غیر این صورت درایه ij در ماترس k با درایه ij در ماتریس k-1 برابر است
الگوریتم بلمن فورد برای یافتن کوتاه ترین مسیرهای هم مبدا بکار میرود. مثلا کوتاه ترین مسیرها از راس A به سایر رئوس که به مراتب کار این الگوریتم بسیار کمتر از فلوید می باشد
روش کار این الگوریتم با فلوید فرق دارد.
این الگوریتم n-1 بار عمل relax رو تمام یالها انجام می دهد(هر بار روی تمام یال ها) در نهایت کوتاه ترین مسیرها از یک راس مشخص با سایر رئوس به دست می آید.
اگر گراف یال منفی داشته باشه هر دو الگوریتم درست کار میکنن البته به شرطی که سیکل منفی وجود نداشته باشد
اگر سیکل منفی وجود داشته باشد هر دو الگوریتم متوجه میشن و اعلام میکنن.
اگر سیکل منفی در گراف وجود داشته باشه دیگه کوتاه ترین مسیر بی معنی میشه

با تشکر فراوان از آقای تیمورپور من یافته های خودم هم اضافه میکنم :
هدف :

• فلوید: یافتن تمام کوتاه ترین مسیرها(کوتاه ترین مسیر بین هر دو راس مشخص) و یک الگوریتم پویا می باشد.
• بلمن فورد: برای یافتن کوتاه ترین مسیرهای هم مبدا بکار میرود.
  

نحوه عملکرد:

• فلوید: ماتریس های A1 تا An رو مرحله به مرحله میسازه و در مرحله K فقط رئوس ۱ تا K رو به عنوان رئوس میان هر دو راس در نظر میگیرد و به این سوال جواب میدهد که آیا راس kام رو بعنوان راس میانی در نظر بگیریم یا نه. اگر با وجود راس kام مسیر کوتاهتر شود آن را در نظر میگیرد در غیر این صورت درایه ij در ماتریس k با درایه ij در ماتریس k-1 برابر است.
• بلمن فورد: این الگوریتم n-1 بار عمل relax رو تمام یالها انجام می دهد(هر بار روی تمام یال ها) در نهایت کوتاه ترین مسیرها از یک راس مشخص با سایر رئوس به دست می آید.
  

پیچیدگی زمانی:

• فلوید: O(v^3)i
• بلمن فورد:
  • کوتاهترین مسیر از راس مبدا تا راس مقصد: O(EV)i
  • کوتاهترین مسیر از راس مبدا تا راس مقصد در صورتیکه راس مبدا بتواند هر کدام از رئوس باشد:O(E*V^2)i
    

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