در گراف وزن دار $G$ با $n$ راس و $m$ یال یک مسیر سخت مسیری است از $u$ به $v$ مانند $u=u_1,u_2,…,u_k=v$ که به ازای $1 \leq i \leq k-2$ داشته باشیم: $w(u_i,u_{i+1} ) \leq w(u_{i+1},u_{i+2})$. با فرض اینکه وزن یال‌ها عددی بین $1$ تا $n^3$ است، الگوریتمی خطی $(O(n+m))$ ارائه دهید که طول کوتاهترین مسیر سخت از راس $s$ به بقیه رووس در گراف $G$ را بیابد.

• سوال بعد
• سوال قبل