سوال ۷۲ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱
اهمیت
۰/۵
فرض کنید G یک گراف بدون جهت و بدون وزن با n رأس و m یال باشد. مسئله زیر را در نظر بگیرید: به‌ازای دو رأس u و v داده شده و پارامتر ورودی k، آیا تعداد کوتاه‌ترین مسیرها بین u و v حداقل k است؟ کدام گزینه در مورد این مسئله درست است؟
پاسخ صحیح: گزینهٔ B — می‌توان الگوریتمی با زمان اجرای O(m+n) برای این مسئله ارائه داد.
پاسخ تشریحی
Key fact. In an unweighted graph the number of distinct shortest paths from a source to every vertex can be computed by a single BFS in time.
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#bfs#shortest-paths#path-counting#linear-time#unweighted-graph#complexity-class