سوال ۱۸

گراف وزن‌دار و جهت‌دار $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$ را بیابد.