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