ডি’এসোপো-পেপ অ্যালগরিদম#

$n$ টি ভার্টেক্স এবং $w_i$ ওয়েট বিশিষ্ট $m$ টি এজের একটি গ্রাফ এবং একটি শুরুর ভার্টেক্স $v_0$ দেওয়া আছে। কাজ হলো ভার্টেক্স $v_0$ থেকে অন্য প্রতিটি ভার্টেক্সে শর্টেস্ট পাথ খুঁজে বের করা।

ডি’এসোপো-পেপ অ্যালগরিদম বেশিরভাগ ক্ষেত্রে ডায়াক্সট্রা অ্যালগরিদম এবং বেলম্যান-ফোর্ড অ্যালগরিদম এর চেয়ে দ্রুত কাজ করবে, এবং নেগেটিভ এজের জন্যও কাজ করবে। তবে নেগেটিভ সাইকেলের জন্য নয়।

বর্ণনা#

$d$ অ্যারেটি শর্টেস্ট পাথের দৈর্ঘ্য ধারণ করুক, অর্থাৎ $d_i$ হলো ভার্টেক্স $v_0$ থেকে ভার্টেক্স $i$ পর্যন্ত শর্টেস্ট পাথের বর্তমান দৈর্ঘ্য। প্রাথমিকভাবে এই অ্যারে প্রতিটি ভার্টেক্সের জন্য অসীম দিয়ে পূর্ণ, $d_{v_0} = 0$ ব্যতীত। অ্যালগরিদম শেষ হওয়ার পর, এই অ্যারে শর্টেস্ট দূরত্ব ধারণ করবে।

$p$ অ্যারেটি বর্তমান পূর্বসূরি ধারণ করুক, অর্থাৎ $p_i$ হলো $v_0$ থেকে $i$ পর্যন্ত বর্তমান শর্টেস্ট পাথে ভার্টেক্স $i$ এর সরাসরি পূর্বসূরি। $d$ অ্যারের মতো, $p$ অ্যারেও অ্যালগরিদম চলাকালীন ক্রমশ পরিবর্তিত হয় এবং শেষে তার চূড়ান্ত মান গ্রহণ করে।

এখন অ্যালগরিদম সম্পর্কে বলা যাক। প্রতিটি ধাপে তিনটি ভার্টেক্স সেট বজায় রাখা হয়:

• $M_0$ - যেসব ভার্টেক্সের দূরত্ব ইতিমধ্যে গণনা করা হয়েছে (যদিও এটি চূড়ান্ত দূরত্ব নাও হতে পারে)
• $M_1$ - যেসব ভার্টেক্সের দূরত্ব বর্তমানে গণনা করা হচ্ছে
• $M_2$ - যেসব ভার্টেক্সের দূরত্ব এখনো গণনা করা হয়নি

$M_1$ সেটের ভার্টেক্সগুলো একটি দ্বিমুখী কিউতে (ডেক) সংরক্ষিত হয়।

অ্যালগরিদমের প্রতিটি ধাপে আমরা $M_1$ সেট থেকে (কিউ-র সামনে থেকে) একটি ভার্টেক্স নিই। ধরা যাক $u$ নির্বাচিত ভার্টেক্স। আমরা এই ভার্টেক্স $u$ কে $M_0$ সেটে রাখি। তারপর আমরা এই ভার্টেক্স থেকে বের হওয়া সমস্ত এজ দিয়ে ইটারেট করি। ধরা যাক $v$ হলো বর্তমান এজের অপর প্রান্ত, এবং $w$ এর ওয়েট।

• যদি $v$ $M_2$ তে থাকে, তাহলে $v$ কে কিউ-র পেছনে ঢুকিয়ে $M_1$ সেটে রাখা হয়। $d_v$ কে $d_u + w$ সেট করা হয়।
• যদি $v$ $M_1$ তে থাকে, তাহলে আমরা $d_v$ এর মান উন্নত করার চেষ্টা করি: $d_v = \min(d_v, d_u + w)$। যেহেতু $v$ ইতিমধ্যে $M_1$ তে আছে, আমাদের এটিকে $M_1$ এবং কিউতে আবার ঢোকানোর প্রয়োজন নেই।
• যদি $v$ $M_0$ তে থাকে, এবং যদি $d_v$ উন্নত করা যায় $d_v > d_u + w$, তাহলে আমরা $d_v$ উন্নত করি এবং ভার্টেক্স $v$ কে কিউ-র শুরুতে রেখে $M_1$ সেটে ফিরিয়ে দিই।

এবং অবশ্যই, $d$ অ্যারেতে প্রতিটি আপডেটের সাথে আমাদের $p$ অ্যারেতে সংশ্লিষ্ট উপাদানও আপডেট করতে হবে।

ইমপ্লিমেন্টেশন#

প্রতিটি ভার্টেক্স বর্তমানে কোন সেটে আছে তা সংরক্ষণ করতে আমরা একটি অ্যারে $m$ ব্যবহার করব।

struct Edge {
    int to, w;
};

int n;
vector<vector<Edge>> adj;

const int INF = 1e9;

void shortest_paths(int v0, vector<int>& d, vector<int>& p) {
    d.assign(n, INF);
    d[v0] = 0;
    vector<int> m(n, 2);
    deque<int> q;
    q.push_back(v0);
    p.assign(n, -1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        m[u] = 0;
        for (Edge e : adj[u]) {
            if (d[e.to] > d[u] + e.w) {
                d[e.to] = d[u] + e.w;
                p[e.to] = u;
                if (m[e.to] == 2) {
                    m[e.to] = 1;
                    q.push_back(e.to);
                } else if (m[e.to] == 0) {
                    m[e.to] = 1;
                    q.push_front(e.to);
                }
            }
        }
    }
}

কমপ্লেক্সিটি#

অ্যালগরিদমটি সাধারণত বেশ দ্রুত কাজ করে - বেশিরভাগ ক্ষেত্রে ডায়াক্সট্রা অ্যালগরিদমের চেয়েও দ্রুত। তবে এমন ক্ষেত্র রয়েছে যেখানে অ্যালগরিদম এক্সপোনেনশিয়াল সময় নেয়, যা এটিকে ওয়ার্স্ট কেসে অনুপযুক্ত করে তোলে। রেফারেন্সের জন্য Stack Overflow এবং Codeforces এর আলোচনা দেখুন।