حل تشریحی سوال شماره 69 طراحی الگوریتم
کنکور ارشد مهندسی کامپیوتر 1400
69.
گراف بدون جهت و وزن‌دار G و راس مشخص s از این گراف را در نظر بگیرید. از الگوریتم دایکسترا برای محسابه کوتاه ترین مسیر ساده s به بقیه رئوس استفاده کرده‌ایم. به ازای چندحالت زیر این الگوریتم با وجود وزن های منفی همیشه درست کار میکند؟
- هر یالی بتواند وزن منفی داشته باشد.
- تنها یال های منتهی به s بتوانند وزن منفی داشته باشند.
- تنها یال های برشی گراف G بتوانند وزن منفی داشته باشند.
- به ازای هر دو از گراف G حداکثر یک یال بتواند وزن منفی داشته باشد.
1)
0
2)
1
3)
2
4)
3
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،