گراف همبند وزندار n راسی و m یالی G داده شده است. میدانیم وزن یالهای این گراف عددی طبیعی و کمتر مساوی m است. f(u,v) برابر کوچکترین عددی است که با یالهای با وزن کمترمساوی آن عدد بتوان از u به v رفت. (f(v,v) را صفر در نظر بگیرید)
راسی مانند s در این گراف مشخص شده است. میخواهیم به ازای هر راس مانند v, f(s,v) را به دست آوریم.
الف) الگوریتمی از O(nlogn+mlogm) ارائه کنید که اعداد خواسته شده را محاسبه کند.
ب) الگوریتمی از O(n+m) ارائه کنید که اعداد خواسته شده را محاسبه کند.