====== سوال ۳ ======

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

  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]