الگوریتم دایکسترا (Dijkstra)

مسئله: کوتاه‌ترین مسیر وزن‌دار

BFS کوتاه‌ترین مسیر را فقط در گراف بدون وزن می‌یابد. اما در واقعیت، جاده‌ها فاصله/زمان متفاوت دارند! اینجاست که دایکسترا می‌درخشد: کوتاه‌ترین مسیر در گراف وزن‌دار با وزن‌های نامنفی.

ایده اصلی — طمع‌کارِ هوشمند

همیشه رأسِ کمترین فاصلهٔ فعلی را پردازش کن؛ وقتی رأسی پردازش شد، فاصله‌اش قطعی است (چون وزن‌ها نامنفی‌اند، راه کوتاه‌تری از این وجود ندارد!).

الگوریتم

1. فاصله شروع = ۰، بقیه = بی‌نهایت
2. رأس با کمترین فاصله را از صف اولویت‌دار بردار
3. فاصله همسایه‌ها را از طریق این رأس به‌روزرسانی (Relax):
   اگر dist[u] + وزن(u,v) < dist[v] → به‌روزرسانی
4. تکرار تا پردازش همه رأس‌ها (یا رسیدن به هدف)

مثال گام‌به‌گام

گراف وزن‌دار (فاصله کیلومتر):
        4
   A -------- B
   |         / |
   2|      3/  |5
   |     /    |
   C -- D --- E
     1     7

دایکسترا از A:
dist = {A:0, B:∞, C:∞, D:∞, E:∞}

پردازش A: C=2, B=4
پردازش C: D=3 (2+1)
پردازش D: B=6? خیر 3+3=6 > 4 نه! E=10 (3+7)
پردازش B: E=9 (4+5) ✓ بهبود از 10!
پردازش E: تمام

نتیجه: A->B:4, A->C:2, A->D:3, A->E:9 (از B)

پیچیدگی

محدودیت مهم: وزن منفی ممنوع!

با یال منفی، فرض «پردازش‌شده = قطعی» می‌شکند و دایکسترا جواب غلط می‌دهد. برای وزن منفی، الگوریتم Bellman-Ford لازم است (O(V·E)).

کاربردهای واقعی

• GPS و مسیریابی: بلیدر، نشان، گوگل‌مپ
• شبکه: مسیر بهینه بسته‌ها (OSPF)
• بازی‌ها: مسیر هوشمند شخصیت‌ها
• لجستیک: کم‌هزینه‌ترین مسیر تحویل

جمع‌بندی

• کوتاه‌ترین مسیر وزن‌دار با وزن نامنفی
• هسته: همیشه کمترین فاصله فعلی را پردازش کن (هیپ)
• O((V+E) log V) با هیپ
• وزن منفی؟ → Bellman-Ford