Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:الگوریتم ها:سوال ۱

سوال ۱

یک گراف ساده‌ی جهت‌دار وزن‌دار داریم. می‌خواهیم کوتاه‌ترین مسیر از s به t را پیدا کنیم. وزن مسیر بین دو رأس u,v به این صورت به دست می‌آید:

فرض کنید یال‌های مسیر به ترتیب e1,e2,,ek باشد. در این صورت وزن مسیر برابر با ki=1ei×2i است.

الگوریتمی از O(n2) ارائه دهید که کم‌وزن‌ترین مسیر بین دو رأس s,t را محاسبه کند.


ابزار صفحه