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

الگوریتم D´Esopo-Pape

گرافی با $n$ رأس و $m$ یال با وزن‌های $w_i$ و یک رأس شروع $v_0$ داده شده است. هدف، پیدا کردن کوتاه‌ترین مسیر از رأس $v_0$ به تمام رئوس دیگر است.

الگوریتم D´Esopo-Pape در بیشتر موارد سریع‌تر از الگوریتم دایکسترا و الگوریتم بلمن-فورد عمل می‌کند و همچنین برای یال‌های با وزن منفی نیز کار می‌کند. اما برای دورهای با وزن منفی کارایی ندارد.

توضیحات

فرض کنید آرایه $d$ طول کوتاه‌ترین مسیرها را نگه دارد، یعنی $d_i$ طول فعلی کوتاه‌ترین مسیر از رأس $v_0$ به رأس $i$ است. در ابتدا این آرایه برای هر رأس با بی‌نهایت پر می‌شود، به جز $d_{v_0} = 0$. پس از پایان الگوریتم، این آرایه حاوی کوتاه‌ترین فاصله‌ها خواهد بود.

فرض کنید آرایه $p$ نیاکان (والدین) فعلی را نگه دارد، یعنی $p_i$ والد مستقیم رأس $i$ در کوتاه‌ترین مسیر فعلی از $v_0$ به $i$ است. همانند آرایه $d$، آرایه $p$ نیز به تدریج در طول الگوریتم تغییر می‌کند و در پایان مقادیر نهایی خود را می‌گیرد.

حال به خود الگوریتم می‌پردازیم. در هر مرحله، سه مجموعه از رئوس نگهداری می‌شوند:

  • $M_0$ - رئوسی که فاصله برای آن‌ها محاسبه شده است (اگرچه ممکن است فاصله نهایی نباشد)
  • $M_1$ - رئوسی که فاصله برای آن‌ها در حال محاسبه است
  • $M_2$ - رئوسی که فاصله برای آن‌ها هنوز محاسبه نشده است

رئوس موجود در مجموعه $M_1$ در یک صف دوطرفه (deque) ذخیره می‌شوند.

در هر مرحله از الگوریتم، یک رأس از مجموعه $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$ برای ذخیره اینکه هر رأس در حال حاضر در کدام مجموعه قرار دارد، استفاده خواهیم کرد.

```cpp file=desopo_pape struct Edge { int to, w; };

int n; vector> adj;

const int INF = 1e9;

void shortest_paths(int v0, vector& d, vector& p) { d.assign(n, INF); d[v0] = 0; vector m(n, 2); deque 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 مراجعه کنید.