الگوریتم دایجسترا (Dijkstra): راهیابی هوشمند در گراف‌ها 🗺️⚡

الگوریتم دایجسترا یکی از مهم‌ترین الگوریتم‌های نظریه گراف است که برای یافتن کوتاه‌ترین مسیر از یک رأس مبدأ به سایر رئوس در گراف‌های وزندار و غیرمنفی استفاده می‌شود. این الگوریتم در سال 1956 توسط ادسخر دایجسترا طراحی شد و امروزه در سیستم‌های مسیریابی مانند گوگل مپس و شبکه‌های کامپیوتری کاربرد فراوان دارد.

1. مقدمه‌ای بر الگوریتم دایجسترا 🧠

الگوریتم دایجسترا یک الگوریتم حریصانه (Greedy) است که:

• ورودی: گراف وزندار با وزن‌های غیرمنفی

• خروجی: کوتاه‌ترین مسیر از مبدأ به همه رئوس دیگر

• مکانیزم: تدریجی و مبتنی بر به‌روزرسانی فاصله‌ها

✨ نکته: این الگوریتم فقط برای گراف‌های بدون یال منفی کار می‌کند.

2. شرایط کاربرد الگوریتم ⚠️

• گراف می‌تواند جهت‌دار یا بی‌جهت باشد

• وزن یال‌ها باید غیرمنفی باشد

• اگر گراف وزن یکسان داشته باشد، معادل BFS عمل می‌کند

3. مراحل اجرای الگوریتم 🔄

1. مقداردهی اولیه:

   • فاصله مبدأ = 0

   • فاصله سایر رئوس = ∞

2. تکرار تا پوشش همه رئوس:

   • انتخاب رأس با کمترین فاصله موقت (حداقل هیپ)

   • به‌روزرسانی فاصله همسایه‌ها:

     
     if فاصله جدید < فاصله فعلی:
         فاصله = فاصله جدید
         پیشین = رأس جاری
     
     

3. نتیجه‌گیری: جدول فاصله‌ها و مسیرها

4. پیاده‌سازی در پایتون 🐍

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        
        if current_dist > distances[current_node]:
            continue
            
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# مثال گراف
graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'A': 2, 'C': 1, 'D': 7},
    'C': {'A': 5, 'B': 1, 'D': 3},
    'D': {'B': 7, 'C': 3}
}

print(dijkstra(graph, 'A'))  # خروجی: {'A': 0, 'B': 2, 'C': 3, 'D': 6}

5. مثال کاربردی 🏙️

فرض کنید می‌خواهیم کوتاه‌ترین مسیر بین شهرها را پیدا کنیم:

✅ کوتاه‌ترین مسیر تهران به اصفهان:
تهران → قم → اصفهان (420km)

6. کاربردهای واقعی 🌍

• مسیریابی در نقشه‌ها (Google Maps)

• شبکه‌های کامپیوتری (پروتکل OSPF)

• سیستم‌های لجستیک و حمل‌ونقل

• طراحی مدارهای الکترونیکی

7. مقایسه با A ⭐*

🚀 A* زمانی بهتر است که هیوریستیک مناسبی در دسترس باشد.

🎯 نتیجه‌گیری

• دایجسترا الگوریتمی پایه‌ای برای یافتن کوتاه‌ترین مسیر

• پیچیدگی زمانی: O((V+E) log V) با استفاده از هیپ

• محدودیت: عدم کارایی برای یال‌های منفی (در این حالت از الگوریتم بلمن-فورد استفاده می‌شود)

پرسش فکری: اگر گراف یال منفی داشته باشد، چرا دایجسترا کار نمی‌کند؟ (پاسخ: به دلیل ماهیت حریصانه ممکن است به نتیجه بهینه نرسد)