حل تشریحی سوال شماره 61 ساختمان داده‌ها

گراف جهت دار و وزن دار G=(E,V) با n راس و O(n) یال و زیرمجموعه $S\subset V$ از راس های گراف با اندازه حداقل $\frac{n}{2}$ داده شده است. فرض کنید وزن تمام یال های گراف مثبت است. به ازای هر راس u از گراف، فاصله راس u از مجموعه S که ان را با d(u,S) نمایش میدهیم عبارت است از:

$d(u,S)=\min \delta \left(u,v\right)$

که در ان $\delta \left(u,v\right)$ برابر با طول کوتاه ترین مسیر جهت دار از u به v در گراف G است. در چه مرتبه زمانی می توان مقادیر d(u,s) را به ازای تمام راس های u از گراف محاسبه کرد؟ دقت کنید که خروجی شامل n مقدار d(u,S) به ازای تمام راس های u از گراف است.(بهترین گزینه را انتخاب کنید)