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

درک الگوریتم

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

مرحله به مرحله محاسبه

فرض کنید ما یک نمودار با گره های A، B، C، D و E و لبه های وزن زیر داریم:

  • A به B: 4
  • A به C: 2
  • B به C: 1
  • B به D: 5
  • C به D: 8
  • C به E: 10
  • D به E: 2

شروع از گره A، شروع مسافت های اولیه: A = 0، دیگران = بی نهایت.مارک همه گره ها به عنوان بدون بازدید.

1

انتخاب گره A (راه 0) به روز رسانی گره های همسایه B و C:

فاصله تا B: 4 (A + 4)، به C: 2 (A + 2). Mark A به عنوان بازدید شده است.

2

انتخاب Node C (راه ۲) به روز رسانی همسایگان D و E:

فاصله تا D: 10 (C + 8)، به E: 12 (C + 10) مارک C به عنوان بازدید شده است.

3

انتخاب گره B (مسیر 4) همسایه به روز رسانی D:

فاصله تا D: 9 (B + 5)، که کمتر از 10. Update D تا 9. Mark B است.

۴

انتخاب گره D (راه 9) همسایه به روز رسانی E:

فاصله تا E: 11 (D + 2). Update E’s فاصله تا 11. Mark D را همانطور که بازدید می شود.

5

گره باقی مانده E دارای فاصله 11. مارک E است که از آن بازدید می شود. کوتاه ترین مسیر از A به E از طریق گره های C، B، D و E با فاصله 11 است.