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

المپدیا

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

ابزار کاربر

ابزار سایت


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

گراف قدرتمند

گراف همبند وزن‌دار n راسی و m یالی G داده شده است. می‌دانیم وزن یال‌های این گراف عددی طبیعی و کمتر مساوی m است. f(u,v) برابر کوچک‌ترین عددی است که با یال‌های با وزن کمتر‌مساوی آن عدد بتوان از u به v رفت. (f(v,v) را صفر در نظر بگیرید)

راسی مانند s در این گراف مشخص شده است. می‌خواهیم به ازای هر راس مانند v, f(s,v) را به دست آوریم.

الف) الگوریتمی از O(nlogn+mlogm) ارائه کنید که اعداد خواسته شده را محاسبه کند.

ب) الگوریتمی از O(n+m) ارائه کنید که اعداد خواسته شده را محاسبه کند.


ابزار صفحه