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

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

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

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

• سوال قبل