سوال 41
حل تشریحی سوال شماره 41 دروس مشترک (ساختمانهای گسسته، ساختمان دادهها، طراحی الگوریتم، مهندسی نرمافزار، شبکههای کامپیوتری)
کنکور ارشد مهندسی فناوری اطلاعات (IT) 1404
41.
فرض کنید یک گراف جهت دار وزن دار داده شده است که شامل n گره و m یال است. این گراف ممکن است دورهای مثبت یا منفی داشته باشد. شما میخواهید یک الگوریتم طراحی کنید که کوتاه ترین مسیر از گره مبدأ s به تمام گره های دیگر را محاسبه کند با رعایت شرایط زیر:
- اگر گراف حاوی یک دور با وزن منفی باشد باید الگوریتم به صورت موثر تشخیص دهد که این دور وجود دارد و نتیجه محاسبه را متوقف کند.
- شما میتوانید از یک صف معمولی (Queue) و یک پشته (Stack) برای مدیریت گره ها و یالها استفاده کنید.
- اگر دور منفی وجود ندارد الگوریتم باید کوتاهترین مسیرها را به درستی محاسبه کند.
پیچیدگی زمانی بدترین حالت این الگوریتم چیست؟
1)
O(n+m)
2)
3)
O(m log n)
4)
O(m.n)
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،