Д´Эсопо-Папегийн алгоритм¶

$w_i$ жинтэй $m$ ирмэг, $n$ оройтой граф ба эхлэх орой $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$ олонлог дахь оройнуудыг хоёр талтай дараалалд (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$ массив дахь харгалзах элементийг ч шинэчлэх ёстой.

Implementation¶

We will use an array $m$ to store in which set each vertex is currently.

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);
                }
            }
        }
    }
}

Complexity¶

Алгоритм ихэвчлэн нэлээд хурдан ажилладаг — ихэнх тохиолдолд Дейкстрагийн алгоритмаас ч хурдан. Гэвч алгоритм экспоненциал хугацаа авдаг тохиолдол байдаг ба энэ нь түүнийг хамгийн муу тохиолдолд тохиромжгүй болгодог. Лавлагаа болгон Stack Overflow ба Codeforces дээрх хэлэлцүүлгийг үзнэ үү.