سوال ۸۳ کنکور ارشد علوم کامپیوتر ۱۴۰۱
اهمیت
۰/۵
G یک گراف وزن‌دار با وزن‌های مثبت و با n رأس است؛ به‌طوری‌که بیشترین درجه رأس‌ها lgn است. کدام الگوریتم برای محاسبه فاصله هر دو رأس از همدیگر مرتبه زمانی بهتری دارد؟ (فرض کنید n به اندازه کافی بزرگ است.)
پاسخ صحیح: گزینهٔ D — n بار دایکسترا (با شروع از هر رأس)
پاسخ تشریحی
We need all-pairs shortest paths in a graph with vertices, positive (hence non-negative) edge weights, and maximum vertex degree .
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#all-pairs-shortest-path#dijkstra#floyd-warshall#bellman-ford#sparse-graph#time-complexity