الگوریتم کوتاهترین مسیر Dijkstra

یکی از الگوریتم ‌ها برای پیدا کردن کوتاه‌ ترین مسیر از گره آغازین تا گره هدف در گراف وزن دار، الگوریتم Dijkstra نام دارد. این الگوریتم یک درخت از کوتاه ‌ترین مسیرها، از راس شروع، تا نقاط دیگر گراف ایجاد می‌کند.

الگوریتم Dijkstra در سال 1959 اختراع شد و نام مخترع دانشمند هلندی خود یعنی ادگار دیکسترا را به خود اختصاص داد. از این الگوریتم می‌توان در گراف های وزن دار استفاده کرد. گراف می‌تواند هم جهت دار و هم غیر جهت دار باشد. تنها شرط لازم برای استفاده از الگوریتم این است که گراف باید در هر یال، وزنی غیر منفی داشته باشد.

تصور کنید دانش‌ آموزی می‌خواهد از کوتاه‌ ترین راه ممکن از خانه به مدرسه برود. او می ‌داند که بعضی از مسیر ها دارای ترافیک سنگینی هستند و استفاده از آن ‌ها مشکل است. در الگوریتم دیکسترا به این معنی است که یال دارای وزن زیادی است--کوتاه‌ترین مسیری که درخت توسط الگوریتم پیدا می‌کند، تلاش می‌کند تا از یال‌ هایی که وزن بیشتری دارند خودداری کند. اگر دانش ‌آموز با استفاده از نقشه به دنبال جهت ها بگردد، این امکان وجود دارد که از الگوریتم دیکسترا همانند الگوریتم ‌های دیگر استفاده کند.

مثال:

در گراف زیر کوتاهترین مسیر از خانه تا مدرسه را بیابید:

گرافی وزن دار که نشان دهنده راه های ممکن از خانه تا مدرسه است.

کوتاهترین مسیری که می توان با استفاده از الگوریتم دیکسترا یافت، به صورت زیر است:

Home => B => D => F => School

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

این الگوریتم از یک گره اولیه و با ساختن مجموعه ای از گره‌ ها که از گره شروع، حداقل فاصله را دارند، درختی با کوتاهترین مسیر پیدا می‌کند.

گراف دارای مشخصات ذیل می ‌باشد:

رأس‌ها، یا گره‌هایی که در الگوریتم با v یا u نشان داده می‌شوند.
یال‌های وزن‌ داری که دو گره را به هم متصل می‌کنند: (u, v) بیانگر یک یال و w(u, v) نمایانگر وزن آن‌ می باشد.

در گراف زیر، وزن هر یک از یال ‌ها با رنگ خاکستری نوشته ‌شده است.

این فرآیند با مقداردهی سه متغیر انجام می‌شود:

dist:

آرایه ای از فاصله ‌ها که از گره شروع یا s تا هرکدام از گره ‌های دیگر گراف به روش زیر مقداردهی اولیه می‌شود:

dist(s) = 0

و برای سایر گره‌ها ∞ = dist(v)

این کار در ابتدا انجام می‌ شود زیرا همچنان که الگوریتم پیش می‌رود، dist از گره شروع تا هر یک از گره های v در گراف بار دیگر از نو محاسبه ‌شده و هنگامی‌که کوتاه ‌ترین مسیر به v پیدا شد، پایان می‌یابد.

صفی از همه گره‌ ها در گراف است. در پایان فرآیند الگوریتم، Q خالی خواهد شد.

مجموعه‌ای خالی است که نشان می‌دهد الگوریتم کدام گره ‌ها را ملاقات کرده است. در پایان اجرای الگوریتم، S حاوی همه گره‌ های گراف خواهد بود.

الگویتم به صورت زیر پیش می رود:

1. هنگامی‌که Q خالی نیست، گره v را که در حال حاضر در S قرار ندارد و دارای کمترین مقدار dist(v) است از Q خارج می کند. در اولین اجرا، گره شروع یا s انتخاب می‌شود زیرا مقدار dist(s) برابر با 0 مقداردهی شده بود. در اجرای بعدی، گره ی بعدی با کمترین مقدار dist (فاصله) انتخاب می‌ شود.

2. برای نشان دادن اینکه v ملاقات شده است، گره v را به S اضافه می کنیم.

3. گره‌های مجاور گره فعلی v را به این صورت به ‌روزرسانی می کنیم: برای هر گره مجاور u:

اگر dist(v) + weight(u, v) < dist(u) باشد، حداقل فاصله جدیدی برای u پیدا می‌شود، بنابراین dist(u) به مقدار جدید فاصله کمینه به ‌روزرسانی می‌ شود.
در غیر این صورت، هیچ به روزرسانی ‌ای برای فاصله dist(u) انجام نمی‌ شود.

الگوریتم همه گره‌ های گراف را ملاقات کرده و کمترین فاصله نسبت به هر گره را پیدا می‌کند. اکنون dist دارای درختی با کمترین فاصله از گره شروع یا s می ‌باشد.

توجه: وزن یال (u, v) از مقادیر مرتبط با (u, v) در گراف گرفته می ‌شود.