پرش به محتویات

الگوریتم دایکسترا روی گراف‌های خلوت

برای صورت مسئله، خود الگوریتم به همراه پیاده‌سازی و اثبات آن را می‌توانید در مقاله الگوریتم دایکسترا پیدا کنید.

الگوریتم

یادآوری می‌کنیم که در استخراج پیچیدگی زمانی الگوریتم دایکسترا از دو عامل استفاده کردیم: زمان پیدا کردن رأس علامت‌نخورده با کمترین فاصله $d[v]$، و زمان عملیات relax کردن، یعنی زمان تغییر مقادیر $d[\text{to}]$.

در ساده‌ترین پیاده‌سازی، این عملیات به ترتیب به زمان $O(n)$ و $O(1)$ نیاز دارند. بنابراین، از آنجایی که عملیات اول را $O(n)$ بار و عملیات دوم را $O(m)$ بار انجام می‌دهیم، به پیچیدگی زمانی $O(n^2 + m)$ رسیدیم.

واضح است که این پیچیدگی برای یک گراف متراکم (dense)، یعنی زمانی که $m \approx n^2$ است، بهینه است. اما در گراف‌های خلوت (sparse)، یعنی زمانی که $m$ بسیار کوچکتر از حداکثر تعداد یال‌ها ($n^2$) است، این پیچیدگی به خاطر بخش اول، دیگر بهینه نیست. بنابراین، لازم است زمان اجرای عملیات اول را بهبود ببخشیم (و البته بدون اینکه تأثیر زیادی روی عملیات دوم بگذاریم).

برای این کار، می‌توانیم از انواع مختلفی از ساختمان داده‌های کمکی استفاده کنیم. کارآمدترین آن‌ها Fibonacci heap است که به عملیات اول اجازه می‌دهد در زمان $O(\log n)$ و به عملیات دوم در زمان $O(1)$ اجرا شود. در نتیجه برای الگوریتم دایکسترا به پیچیدگی $O(n \log n + m)$ می‌رسیم که حداقل پیچیدگی نظری برای مسئله جستجوی کوتاه‌ترین مسیر نیز هست. بنابراین این الگوریتم بهینه عمل می‌کند و Fibonacci heapها ساختمان داده بهینه‌ای هستند. هیچ ساختمان داده‌ای وجود ندارد که بتواند هر دو عملیات را در زمان $O(1)$ انجام دهد، زیرا این کار امکان مرتب‌سازی یک لیست از اعداد تصادفی در زمان خطی را فراهم می‌کرد که غیرممکن است. جالب اینجاست که الگوریتمی از Thorup وجود دارد که کوتاه‌ترین مسیر را در زمان $O(m)$ پیدا می‌کند، اما فقط برای وزن‌های صحیح کار می‌کند و از ایده‌ای کاملاً متفاوت استفاده می‌کند. بنابراین این موضوع هیچ تناقضی ایجاد نمی‌کند. Fibonacci heapها پیچیدگی بهینه‌ای برای این کار فراهم می‌کنند. با این حال، پیاده‌سازی آن‌ها بسیار پیچیده است و همچنین ضریب ثابت پنهان بزرگی دارند.

به عنوان یک راه حل میانه، می‌توانید از ساختمان داده‌هایی استفاده کنید که هر دو نوع عملیات (استخراج کمینه و به‌روزرسانی یک آیتم) را در زمان $O(\log n)$ انجام می‌دهند. در این صورت پیچیدگی الگوریتم دایکسترا $O(n \log n + m \log n) = O(m \log n)$ خواهد بود.

زبان C++ دو نوع از این ساختمان داده‌ها را فراهم می‌کند: set و priority_queue. اولی بر اساس درخت‌های قرمز-سیاه (red-black trees) و دومی بر اساس هیپ (heap) است. بنابراین priority_queue ضریب ثابت پنهان کوچکتری دارد، اما یک عیب هم دارد: از عملیات حذف یک عنصر پشتیبانی نمی‌کند. به همین دلیل باید از یک «راه‌حل جایگزین» استفاده کنیم که در واقع منجر به یک ضریب کمی بدتر $\log m$ به جای $\log n$ می‌شود (اگرچه از نظر پیچیدگی یکسان هستند).

پیاده‌سازی

set

با کانتینر set شروع می‌کنیم. از آنجایی که باید رئوس را بر اساس مقادیرشان در آرایه $d[]$ مرتب نگه داریم، مناسب است که زوج‌های واقعی را ذخیره کنیم: فاصله و اندیس رأس. در نتیجه، در یک set، زوج‌ها به طور خودکار بر اساس فاصله‌شان مرتب می‌شوند.

const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);

    d[s] = 0;
    set<pair<int, int>> q;
    q.insert({0, s});
    while (!q.empty()) {
        int v = q.begin()->second;
        q.erase(q.begin());

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                q.erase({d[to], to});
                d[to] = d[v] + len;
                p[to] = v;
                q.insert({d[to], to});
            }
        }
    }
}

دیگر به آرایه $u[]$ از پیاده‌سازی عادی الگوریتم دایکسترا نیازی نداریم. ما از set برای ذخیره آن اطلاعات و همچنین پیدا کردن رأس با کوتاه‌ترین فاصله استفاده خواهیم کرد. این ساختار تا حدی شبیه به یک صف عمل می‌کند. حلقه اصلی تا زمانی اجرا می‌شود که هیچ رأس دیگری در set/صف باقی نمانده باشد. رأسی با کمترین فاصله استخراج می‌شود و برای هر عملیات relax موفق، ابتدا زوج قدیمی را حذف کرده و سپس پس از relax، زوج جدید را به صف اضافه می‌کنیم.

priority_queue

تفاوت اصلی با پیاده‌سازی با set این است که در بسیاری از زبان‌ها، از جمله C++، نمی‌توانیم عناصری را از priority_queue حذف کنیم (اگرچه هیپ‌ها در تئوری می‌توانند از این عملیات پشتیبانی کنند). بنابراین، باید از یک راه‌حل جایگزین استفاده کنیم: ما به سادگی زوج قدیمی را از صف حذف نمی‌کنیم. در نتیجه، یک رأس می‌تواند چندین بار با فاصله‌های مختلف به طور همزمان در صف ظاهر شود. از میان این زوج‌ها، ما فقط به زوج‌هایی علاقه‌مندیم که عنصر اول آن‌ها برابر با مقدار متناظر در $d[]$ باشد؛ تمام زوج‌های دیگر قدیمی هستند. بنابراین، باید یک تغییر کوچک ایجاد کنیم: در ابتدای هر تکرار، پس از استخراج زوج بعدی، بررسی می‌کنیم که آیا این یک زوج مهم است یا یک زوج قدیمی و پردازش‌شده. این بررسی مهم است، در غیر این صورت پیچیدگی زمانی می‌تواند تا $O(n m)$ افزایش یابد.

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

const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);

    d[s] = 0;
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

در عمل، نسخه با priority_queue کمی سریع‌تر از نسخه با set است.

جالب اینجاست که یک گزارش فنی در سال ۲۰۰۷ به این نتیجه رسید که نسخه‌ای از الگوریتم که از عملیات decrease-key استفاده نمی‌کند، سریع‌تر از نسخه با decrease-key اجرا می‌شود و این اختلاف عملکرد برای گراف‌های خلوت بیشتر است.

خلاص شدن از زوج‌ها

می‌توانید با ذخیره نکردن زوج‌ها در کانتینرها و تنها ذخیره کردن اندیس رئوس، عملکرد را کمی بیشتر بهبود ببخشید. در این حالت، باید عملگر مقایسه را overload کنیم: این عملگر باید دو رأس را با استفاده از فاصله‌های ذخیره شده در $d[]$ مقایسه کند.

در نتیجه عملیات relax، فاصله برخی از رئوس تغییر خواهد کرد. اما ساختمان داده به طور خودکار خود را دوباره مرتب نمی‌کند. در واقع، تغییر فاصله رئوس در صف ممکن است ساختار داده را از بین ببرد. مانند قبل، باید رأس را قبل از relax کردن حذف کرده و سپس دوباره آن را درج کنیم.

از آنجایی که فقط می‌توانیم از set حذف کنیم، این بهینه‌سازی فقط برای روش با set قابل اجرا است و با پیاده‌سازی priority_queue کار نمی‌کند. در عمل این کار عملکرد را به طور قابل توجهی افزایش می‌دهد، به خصوص زمانی که از انواع داده بزرگتر مانند long long یا double برای ذخیره فاصله‌ها استفاده می‌شود.