گراف وزن‌دار و جهت‌دار ‎$G$‎ با وزن‌های حقیقی و مثبت داده شده است. می‌دانیم که رئوس ‎$W=\{ w_1,\ldots,w_k \}$‎ در ‎$G$‎ هستند که وقتی حذف شوند، ‎$G$‎ تبدیل به ‎DAG (گراف جهت دار بدون دور) می‌شود ‎($1 \le k < |V|$)‎.

راس ‎$s \in V-W$‎ را در نظر بگیرید. الگوریتمی از ‎$O(k(|V|+|E|))$‎ ارائه کنید که با گرفتن ‎$G$‎، ‎$W$‎ و ‎$s$‎ کم‌وزن‌ترین مسیر جهت‌دار از ‎$s$‎ به تمام رئوس دیگر ‎$G$‎ را بیابد.

• سوال قبل