سوال ۶۵ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

اهمیت

۰/۵

کدام‌یک از مسائل زیر را می‌توان در زمان $O\left(n^{۲/۵}\right)$ حل کرد؟

الف) پیداکردن کوتاه‌ترین مسیر بین هر دو رأس در گراف وزن‌دار با $n$ رأس

ب) ضرب دو ماتریس $n \times n$

ج) پیداکردن تعداد جفت رئوسی که همسایهٔ مشترک دارند در یک گراف $n$ رأسی

#matrix-multiplication#matrix-multiplication-exponent#all-pairs-shortest-paths#common-neighbors#adjacency-matrix-squared#subcubic-algorithms