زمان کنونی: ۰۳ دى ۱۴۰۳, ۰۸:۲۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال از مبحث گراف

ارسال:
  

ziba.O پرسیده:

سوال از مبحث گراف

۳ الگوریتم زیرو در نظر بگیرید:
۱/ فلوید ۲/ دایکسترا ۳/ بلمن فورد
حالا چند تا سوال دارم ممنون میشم جواب بدین.
سوال اول: کدامیک توانایی کار با گراف با وزن منفی را دارند؟
سوال دوم: کدامیک توانایی کار با گراف با دور منفی را دارند؟
سوال سوم: کدامیک توانایی تشخیص دور منفی را دارند؟
سوال چهارم: مرتبه زمانی هر کدام و ترتیب بر حسب مرتبه زمانی ۳ الگوریتم گفته شده.
تشکر دوستان
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

moloodi پاسخ داده:

RE: سوال از مبحث گراف

سلام.
- بلمن فورد می تواند با یال منفی کار کند.
- دایکسترا نمی تواند با یال منفی کار کند (دایکسترا در شرایط خاص می تواند)
- اگر در گراف، یال با وزن منفی داشته باشیم فلوید ممکن است جواب درست تولید نکند.

- بلمن فورد توانایی تشخیص دور منفی را دارد. (در گرافی که دور منفی دارد پیدا کردن کوتاهترین مسیر معنا ندارد)
- فلوید می تواند دور منفی را پیدا کند البته در روش کلاسیک این ویژگی وجود نداره ولی با اضافه کردن چند خط اضافه در پایان الگوریتم می توان به آن دست پیدا کرد.
- مرتبه دایکسترا به ساختمان داده مورد استفاده وابستگی دارد اگر از ماتریس مجاورت استفاده کنیم مرتبه (O(n^2 خواهد بود اما می توان از سایر ساختمان داده ها هم استفاده کرد مثلا اگر از هیپ فیبوناچی استفاده کنیم مرتبه (O(E + VLogV خواهد بود و اگر از هیپ باینری استفاده کنیم از مرتبه (O((E+V)LogV می باشد.
مرتبه بلمن فورد (O(VE
مرتبه فلوید (O(N^3
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مبحث جستجوهای محلی Elham_tm ۷ ۴,۵۲۹ ۱۷ اسفند ۱۴۰۰ ۰۵:۴۳ ب.ظ
آخرین ارسال: KB2000
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۲,۱۵۰ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۲,۰۵۸ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  طراحی گرافیکی simaakbari ۰ ۲,۵۰۰ ۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ
آخرین ارسال: simaakbari
  کوتاه ترین مسیر در گراف Sanazzz ۳ ۴,۲۲۳ ۰۷ فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ
آخرین ارسال: Sanazzz
  کتاب خوب در باره نظریه گراف ماهی ۲۵۸ ۰ ۲,۰۲۱ ۲۸ شهریور ۱۳۹۷ ۱۲:۲۸ ب.ظ
آخرین ارسال: ماهی ۲۵۸
  یافتن مسیر در گراف کامل دو بخشی Sepideh96 ۳ ۴,۲۲۵ ۲۶ بهمن ۱۳۹۶ ۱۲:۴۲ ب.ظ
آخرین ارسال: αɾια
  مبحث شار، بیشینه جریان، الگوریتم Ford-Fulkerson Sepideh96 ۲ ۲,۸۹۰ ۰۳ بهمن ۱۳۹۶ ۰۴:۴۷ ق.ظ
آخرین ارسال: Sepideh96
  رنگ آمیزی راسهای گراف ss311 ۲ ۲,۴۳۱ ۰۳ بهمن ۱۳۹۶ ۰۱:۲۳ ق.ظ
آخرین ارسال: ss311
  سوال در مورد ساختن یک گراف دانش محدود zahra89 ۰ ۱,۷۲۷ ۰۲ بهمن ۱۳۹۶ ۰۳:۴۱ ب.ظ
آخرین ارسال: zahra89

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close