در گراف وزن دار G با n راس و m یال یک مسیر سخت مسیری است از u به v مانند u=u1,u2,…,uk=v که به ازای 1≤i≤k−2 داشته باشیم: w(ui,ui+1)≤w(ui+1,ui+2). با فرض اینکه وزن یالها عددی بین 1 تا n3 است، الگوریتمی خطی (O(n+m)) ارائه دهید که طول کوتاهترین مسیر سخت از راس s به بقیه رووس در گراف G را بیابد.