یک گراف سادهی جهتدار وزندار داریم. میخواهیم کوتاهترین مسیر از s به t را پیدا کنیم. وزن مسیر بین دو رأس u,v به این صورت به دست میآید:
فرض کنید یالهای مسیر به ترتیب e1,e2,…,ek باشد. در این صورت وزن مسیر برابر با ∑ki=1ei×2i است.
الگوریتمی از O(n2) ارائه دهید که کموزنترین مسیر بین دو رأس s,t را محاسبه کند.