دکسترا
============
صورت مسئله
------------

یک گراف جهت دار وزن دار 
:math:`G`
داریم. وزن تمامی یال های :math:`G` نامنفی می باشند.

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

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

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

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

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


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

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

راه اول با اردر :math:`\mathcal{O}(n^2)`
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

در هر مرحله روی کل رئوس انتخاب نشده حلقه اجرا کنیم و کمینه را پیدا کنیم. در هر مرحله از فرایند ما 
:math:`\mathcal{O}(n)`
انجام میدهیم. چون الگوریتم دارای :math:`n` مرحله است اردر برنامه ما 
:math:`\mathcal{O}(n^2)`
میشود.


راه دوم با اردر :math:`\mathcal{O}(n + m.lg(n))`
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

در هر مرحله به جای اجرای حلقه رو کل رئوس، از داده ساختار هایی استفاده میکنیم که کمینه را سریع تر پیدا بکنند. مانند :math:`set` و :math:`priority-queue` در :math:`C++`.( فرض کنید در اینجااز :math:`set` استفاده میکنیم)

در هر مرحله کمینه مقدار :math:`dis` را میتوان با 
:math:`\mathcal{O}(1)`
پیدا کرد. هر بار که مقدار خانه ای از :math:`dis` را عوض میکنیم باید مقدار ان را در :math:`set` اپدیت کنیم که  از اردر
:math:`\mathcal{O}(lg(n))`
میباشد.

چون ممکن است هر مرحله به اندازه تعداد همسایه های راس انتخاب شده خانه های :math:`dis` عوض بشود پس ما به انداره مجموع تعداد همسایه های کل رئوس مقادیر :math:`dis` را عوض میکنیم. میدانیم جمع تعداد همسایه ها از
:math:`\mathcal{O}(m)`
است. پس در کل 
:math:`\mathcal{O}(m.log(n))`
هزینه زمانی به ازای اپدیت ها میدهیم پس اردر برنامه :math:`\mathcal{O}(n + m.lg(n))` میشود.