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

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

برای گراف‌های بدون وزن، جست‌وجوی سطح‌اول (BFS) جواب می‌دهد: اول یک قدم دورتر را بگرد، بعد دو قدم، بعد سه قدم. وزن‌ها این را خراب می‌کنند. مسیری با سه یالِ ارزان می‌تواند از مسیری با یک یالِ گران بهتر باشد؛ پس «کمترین تعداد قدم» دیگر یعنی «کوتاه‌ترین» نیست. الگوریتم دایکسترا (Dijkstra) که ادسخر دایکسترا در سال ۱۹۵۹ منتشرش کرد، این مشکل را با یک قاعده حل می‌کند: همیشه نزدیک‌ترین گرهِ تمام‌نشده را بعد از همه گسترش بده.

این مقاله الگوریتم را در پایتون می‌سازد، آن را روی یک گراف واقعی دنبال می‌کند، توضیح می‌دهد چرا کار می‌کند و به جزئیاتی می‌پردازد که نسخهٔ کتاب درسی را از نسخه‌ای که می‌شود به آن اعتماد کرد جدا می‌کند: ورودی‌های کهنه در هیپ، تساوی‌ها، وزن‌های منفی و پیچیدگی. باید با Big-O (نماد Big-O با کد واقعی) و دیکشنری‌های پایتون راحت باشید.

گراف نمونه#

شش مکان که با جاده به هم وصل‌اند و روی هر جاده زمانِ سفر نوشته شده. جاده‌ها دوطرفه‌اند.

گراف را به شکل یک نقشهٔ مجاورت (adjacency map) نگه می‌داریم: برای هر گره، دیکشنری‌ای از همسایه‌ها و وزنِ یال‌ها.

from collections import defaultdict

edges = [("A", "B", 4), ("A", "C", 2), ("B", "C", 1), ("B", "D", 5), ("C", "D", 8),
         ("C", "E", 10), ("D", "E", 2), ("D", "F", 6), ("E", "F", 2)]

graph = defaultdict(dict)
for u, v, w in edges:
    graph[u][v] = w
    graph[v][u] = w      # undirected: add both directions

ایده#

برای هر گره یک فاصلهٔ موقت نگه دارید: ۰ برای مبدأ و بی‌نهایت برای بقیه. بعد این را تکرار کنید:

1. گرهِ تمام‌نشده‌ای را که کمترین فاصلهٔ موقت را دارد انتخاب کنید. فاصلهٔ آن حالا نهایی است.
2. همهٔ یال‌هایش را آزادسازی (relax) کنید: اگر عبور از این گره فاصلهٔ کوتاه‌تری از فاصلهٔ فعلیِ یک همسایه به او می‌دهد، همسایه را به‌روز کنید.

تنها بخشِ سخت مرحلهٔ ۱ است: پیدا کردنِ سریعِ کمترین فاصله. پیمایشِ همهٔ گره‌ها در هر مرحله O(V) هزینه دارد. یک صف اولویت (یک هیپ دودویی) آن را به O(log V) می‌رساند.

پیاده‌سازی#

ماژول heapq پایتون یک لیستِ ساده را به یک min-heap تبدیل می‌کند. این ماژول عملیاتِ «کاهش کلید» (decrease key) ندارد؛ پس وقتی فاصلهٔ یک گره بهتر می‌شود، فقط یک ورودیِ جدید push می‌کنیم و ورودیِ قدیمی را در هیپ رها می‌کنیم. وقتی ورودیِ قدیمی بالاخره بیرون می‌آید، آن را کهنه (stale) تشخیص می‌دهیم و از آن رد می‌شویم. به این حذف تنبل (lazy deletion) می‌گویند و تقریباً همهٔ پیاده‌سازی‌های پایتون همین‌طور کار می‌کنند.

import heapq

def dijkstra(graph, source):
    dist = {source: 0}
    prev = {}                             # prev[node] = the node we reached it from
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue                      # stale entry: we already found a shorter way here
        for neighbor, weight in graph[node].items():
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float("inf")):
                dist[neighbor] = new_dist
                prev[neighbor] = node
                heapq.heappush(heap, (new_dist, neighbor))
    return dist, prev

>>> dist, prev = dijkstra(graph, "A")
>>> dist
{'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 12}

گره‌هایی که از مبدأ نمی‌شود به آن‌ها رسید، اصلاً در dist ظاهر نمی‌شوند.

بازسازیِ مسیر#

dist طولِ هر کوتاه‌ترین مسیر را می‌دهد؛ prev اجازه می‌دهد خودِ مسیر را با حرکت به عقب از مقصد بازسازی کنیم:

def path_to(prev, source, target):
    path = [target]
    while path[-1] != source:
        path.append(prev[path[-1]])       # KeyError means target is unreachable
    return path[::-1]

>>> path_to(prev, "A", "F")
['A', 'C', 'B', 'D', 'E', 'F']

اشاره‌گرهای prev یک درخت کوتاه‌ترین مسیر با ریشهٔ مبدأ می‌سازند: همان یال‌های برجسته در نمودار. دقت کنید بهترین مسیر به B جادهٔ مستقیم (۴) نیست، بلکه دور زدن از طریق C است (۲ + ۱ = ۳).

دنبال کردنِ قدم‌به‌قدم#

این همهٔ عملیات‌های هیپ برای گراف ماست. به ورودی‌های کهنه دقت کنید: B، D، E و F هر کدام دو بار push می‌شوند، چون بعد از push اول مسیرِ کوتاه‌تری پیدا شده.

چرا درست است#

ادعای اصلی این است: وقتی گره‌ای با فاصلهٔ فعلی‌اش d از هیپ بیرون می‌آید، هیچ مسیرِ کوتاه‌تری به آن وجود ندارد.

فرض کنید مسیرِ کوتاه‌تری وجود داشت. این مسیر از مبدأ (که از قبل نهایی شده) شروع می‌شود و به گرهِ ما ختم می‌شود؛ پس جایی در طول آن اولین گرهی هست که هنوز نهایی نشده؛ اسمش را u بگذارید. بخشی از مسیر که قبل از u است از گره‌های نهایی‌شده می‌گذرد؛ پس u با همان فاصله آزادسازی شده و با کلیدی در هیپ نشسته که از طولِ مسیر تا u بیشتر نیست. چون همهٔ وزن‌ها نامنفی‌اند، یال‌های باقی‌مانده فقط می‌توانند به آن اضافه کنند؛ پس کلیدِ u حداکثر به اندازهٔ طولِ آن مسیرِ کوتاه‌تر است، که از d کمتر است. اما در این صورت هیپ باید u را قبل از گرهِ ما به ما می‌داد. تناقض.

این استدلال دقیقاً به یک فرض تکیه دارد: وزن‌های نامنفی. آن را بردارید تا کل ماجرا فرو بریزد.

یال‌های منفی خرابش می‌کنند#

graph = {"A": {"B": 2, "C": 3}, "B": {"D": 2}, "C": {"B": -2}, "D": {}}

فاصلهٔ واقعی تا B برابر ۱ است (A → C → B) و تا D برابر ۳. اما دایکسترا B (با فاصلهٔ ۲) را قبل از C (با فاصلهٔ ۳) بیرون می‌کشد؛ پس B را تمام‌شده حساب می‌کند پیش از آنکه مسیرِ ارزان‌تر از طریق C دیده شود. نسخه‌های کتاب درسی که گره‌ها را «تمام‌شده» علامت می‌زنند B = 2 و D = 4 برمی‌گردانند، که غلط است.

نسخهٔ تنبلِ ما اینجا اتفاقاً خودش را درست می‌کند، چون وقتی فاصلهٔ کوتاه‌تر پیدا می‌شود B را دوباره push می‌کند و بعد B را دوباره پردازش می‌کند. به این تکیه نکنید: با یال‌های منفی یک گره ممکن است بارها و بارها دوباره پردازش شود و روی گراف‌های بدخواهانه زمان اجرا نمایی می‌شود. اگر گرافتان ممکن است وزن منفی داشته باشد، از الگوریتم Bellman–Ford با پیچیدگی O(V·E) استفاده کنید که دورهای منفی را هم تشخیص می‌دهد؛ جایی که اصلاً کوتاه‌ترین مسیری وجود ندارد.

پیچیدگی#

هر گره فقط یک بار پردازش می‌شود (ورودی‌های بعدی‌اش به‌عنوان کهنه رد می‌شوند)؛ پس هر یال حداکثر یک بار در هر جهت آزادسازی می‌شود و حداکثر یک push ایجاد می‌کند. در نتیجه هیپ O(E) ورودی دارد و هر push و pop هزینهٔ O(log E) دارد. چون E حداکثر V² است، log E حداکثر 2 log V است، که نتیجه می‌دهد:

• زمان: O((V + E) log V) با یک هیپ دودویی.
• حافظه: O(V + E) برای گراف، فاصله‌ها و هیپ.

برای گراف‌های چگال، که E نزدیک به V² است، یک نسخهٔ ساده‌ترِ O(V²) بدون هیپ در واقع سریع‌تر است: یک آرایه از فاصله‌ها نگه دارید و هر بار برای پیدا کردنِ کمینه آن را پیمایش کنید. ساختارهای نظری مثل هیپ فیبوناچی به O(E + V log V) می‌رسند، اما سربارشان در عمل به‌ندرت می‌ارزد.

جزئیات عملی#

زود متوقف شوید. اگر فقط مسیر به یک مقصد را لازم دارید، به محض اینکه آن را pop کردید برگردید. فاصله‌اش در همان لحظه نهایی است و روی یک گراف بزرگ می‌توانید از بیشترِ کار صرف‌نظر کنید:

        d, node = heapq.heappop(heap)
        if node == target:
            return d

تساوی در هیپ. ورودی‌های هیپ تاپل‌اند؛ پس وقتی دو فاصله برابرند پایتون خودِ گره‌ها را مقایسه می‌کند. برای رشته‌ها و عددها مشکلی نیست، اما اشیائی که از < پشتیبانی نمی‌کنند TypeError می‌دهند. یک شمارنده را به‌عنوان معیارِ دوم اضافه کنید:

from itertools import count

tiebreak = count()
heapq.heappush(heap, (new_dist, next(tiebreak), neighbor))

وزن‌های اعشاری. با وزن‌های float، دو مسیرِ «هم‌طول» ممکن است به‌خاطر خطای گرد کردن کمی فرق کنند. وقتی خودِ مسیر دقیقاً مهم است، با یک حدِ تحمل مقایسه کنید یا به عددهای صحیح (سانتی‌متر، میلی‌ثانیه) تبدیل کنید.

قدم‌های بعدی#

• الگوریتم A* همان دایکسترا به‌علاوهٔ یک تابع تخمین (heuristic) است: هیپ را بر اساس distance + estimate_to_target مرتب می‌کند. با یک تخمینِ خوب (مثل فاصلهٔ خط مستقیم روی نقشه) گره‌های بسیار کمتری را می‌گردد و همچنان کوتاه‌ترین مسیر را پیدا می‌کند، به شرطی که تخمین هرگز بیشتر از مقدار واقعی نباشد.
• مسیریابیِ شبکه مستقیماً از دایکسترا استفاده می‌کند: روترهای OSPF با آن کوتاه‌ترین مسیرها را روی نقشهٔ شبکه حساب می‌کنند.
• شبکه‌های جاده‌ای در مقیاس یک قاره از تکنیک‌های پیش‌پردازش مثل contraction hierarchies استفاده می‌کنند که در هسته‌شان جست‌وجوهایی به سبک دایکسترا هست.

جمع‌بندی#

• دایکسترا کوتاه‌ترین مسیرها را از یک مبدأ در گراف‌هایی با وزن یالِ نامنفی پیدا می‌کند.
• همیشه نزدیک‌ترین گرهِ تمام‌نشده را گسترش دهید؛ یک min-heap (heapq) آن را در O(log V) پیدا می‌کند.
• بدون decrease-key، ورودی‌های تکراری push کنید و از ورودی‌های کهنه رد شوید (if d > dist[node]: continue).
• اشاره‌گرهای prev را برای بازسازیِ مسیرها نگه دارید؛ این‌ها یک درخت کوتاه‌ترین مسیر می‌سازند.
• زمان اجرا O((V + E) log V) است؛ برای یال‌های منفی از Bellman–Ford و برای گراف‌های خیلی چگال از پیمایشِ آرایه با O(V²) استفاده کنید.