خبرگزاری آیصد (جدیدترین و جذاب ترین اخبار ایران و جهان)

نشر توسط:admin Views 41 تاریخ : 2 خرداد 1395

الگوریتم دایجسترا یا دیکسترا :این الگوریتم هم یکی از الگوریتم های پیمایش گراف است که مسئله ی کوتاهترین مسیر از مبداء واحد را برای گراف های وزن داری که یال با وزن منفی ندارند، را حل می کند.

در این الگوریتم یک گره  مثلا گره شماره ی یک به عنوان مبداء تعیین شده سپس این گره با همه ی یال های(i) مقایسه شده و وزن یال مرتبط با گره یک در [D[i قرار می گیرد.سپس برای هر گرهV حلقه ی for تکرار می شود.

([D[w]=min(D[w],D[v]+L[v,w

این الگوریتم مشابه الگوریتم پریم، برای بدست آوردن درخت پوشای مینیمم،می باشد.در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی کند و می بایست از الگوریتم های دیگر نظیر بلمن-فورد اگرچه مرتبه ی زمانی بیشتری دارند استفاده کرد.

مرتبه زمانی:

O(n^2)