یک گراف ساده‌ی جهت‌دار وزن‌دار داریم. می‌خواهیم کوتاه‌ترین مسیر از $s$ به $t$ را پیدا کنیم. وزن مسیر بین دو رأس $u, v$ به این صورت به دست می‌آید:

فرض کنید یال‌های مسیر به ترتیب $e_1, e_2, \ldots, e_k$ باشد. در این صورت وزن مسیر برابر با $\sum_{i=1}^k e_i \times 2^i$ است.

الگوریتمی از $O(n^2)$ ارائه دهید که کم‌وزن‌ترین مسیر بین دو رأس $s, t$ را محاسبه کند.

• سوال بعد