دکسترا¶

صورت مسئله¶

یک گراف جهت دار وزن دار \(G\) داریم. وزن تمامی یال های \(G\) نامنفی می باشند.

حال میخواهیم به ازای هر راس طول کوتاه ترین مسیر از راس \(sc\) به بقیه رئوس را پیدا کنیم که طول یک مسیر برابر جمع وزن های یال های آن است.

الگوریتم دایکسترا¶

یک آرایه به نام \(dis\) تعریف میکنیم. در هنگام انجام الگوریتم، \(dis_u\) نشان دهنده کوتاه ترین مسیر به راس \(u\) است که راس قبلی مسیر حتما انتخاب شده باشد.(انتخاب شدن در جلوتر توضیح داده میشود). در ابتدا همه خانه های ارایه \(dis\) برابر \(\infty\) است. ابتدا میدانیم \(dis_{sc} = 0\) است. حال \(sc\) را انتخاب میکنیم حال \(dis\) رئوس همسایه \(sc\) را اپدیت میکنیم.

حال در مرحله از الگوریتم از بین رئوسی که تا حالا انتخاب نکرده ایم آن راسی را انتخاب میکنیم که مقدار \(dis\) آن کمینه است و آن را \(v\) مینامیم.

حال اثبات میکنیم که طول کوتاه ترین مسیر از \(sc\) به \(v\) همان مقدار فعلی \(dis_v\) است. برای این کار از برهان خلف استفاده میکنیم و فرض میکنیم مسیر کوتاه تری وجود دارد (مسیری به طول \(P\)). اخرین راس انتخاب شده در این مسیر را بگیرید و آن را \(last\) بنامید. (حتما وجود دارد چون راس \(sc\) انتخاب شده است.) راس بعدی \(last\) را \(u\) مینامیم. (راس بعدی نیز وجود دارن چون راس اخر انتخاب نشده بود).

طبق فرض خلف طول مسیر تا \(v\) کمتر از \(dis_v\) بوده و چون یال ها منفی نیستند طول مسیر تا \(u\) نیز کمتر از \(dis_v\) است. چون راس قبلی \(u\) در مسیر راسی انتخاب شده بوده و فاصله نهایی راس های انتخاب شده همان \(dis\) آن ها است، آنگاه \(dis_u\) در زمان انتخاب شدن \(last\) برابر طول کوتاهترین تا \(u\) شده است. و چون \(dis_u < P\) و \(P < dis_v\) است پس \(dis_u < dis_v\) می باشد که با کمینه بودن \(dis_v\) در بین مقدار های فعلی در تناقض است. پس فرض خلف ما غلط بوده و حکم اثبات میشود.

حال که اثبات شد مقدار \(dis_v\) دقیقا برابر طول کوتاهترین مسیر به \(v\) است، آنرا انتخاب کرده سپس به ازای تمام همسایه های آن مانند \(adj\) که یال از \(v\) به \(adj\) وزن \(w\) دارد، \(dis_{adj} = min(dis_{adj}, dis_v + w)\) را انجام میدهیم. و همین فرآیند را ادامه میدهیم تا همه رئوس انتخاب شده باشند.

تحلیل اردر¶

برای این الگوریتم دو راه کلی پیاده سازی وجود دارد.