Агуулгыг алгасах

0-1 BFS

Жингүй граф дээр Өргөнөөр эхлэх хайлт ашиглан ганц эх ба бусад бүх оройн хоорондох хамгийн богино замыг $O(|E|)$-д олж болох нь сайн мэдэгдэнэ, өөрөөр хэлбэл зай гэдэг нь эхээс өөр орой хүртэл туулах шаардлагатай ирмэгийн хамгийн бага тоо юм. Бид ийм графыг ирмэг бүр нь $1$ жинтэй байх жинтэй граф гэж ч тайлбарлаж болно. Хэрэв графын бүх ирмэг ижил жинтэй биш бол бидэнд $O(|V|^2 + |E|)$ эсвэл $O(|E| \log |V|)$ хугацаанд ажилладаг Дейкстра шиг илүү ерөнхий алгоритм хэрэгтэй.

Гэвч хэрэв жингүүд илүү хязгаарлагдмал бол бид ихэвчлэн илүү сайн хийж чадна. Энэ өгүүлэлд бид ирмэг бүрийн жин $0$ эсвэл $1$ байвал SSSP (ганц эхээс гарах хамгийн богино зам) бодлогыг $O(|E|)$-д бодоход BFS-г хэрхэн ашиглаж болохыг үзүүлнэ.

Алгоритм

Бид Дейкстрагийн алгоритмыг нарийн судалж, бидний тусгай граф ямар үр дагавар авчирдгийг бодох замаар алгоритмыг боловсруулж болно. Дейкстрагийн алгоритмын ерөнхий хэлбэр нь (энд тэргүүлэх эрхийн дараалалд set ашигласан):

d.assign(n, INF);
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 u = edge.first;
        int w = edge.second;

        if (d[v] + w < d[u]) {
            q.erase({d[u], u});
            d[u] = d[v] + w;
            q.insert({d[u], u});
        }
    }
}

Эх s ба дараалал дахь бусад хоёр оройн хоорондох зайнуудын ялгаа хамгийн ихдээ нэгээр ялгаатай болохыг бид анзаарч болно. Тухайлбал бид $u \in Q$ бүрийн хувьд $d[v] \le d[u] \le d[v] + 1$ болохыг мэднэ. Үүний шалтгаан нь бид итерац бүрийн явцад дараалалд зөвхөн тэнцүү зайтай эсвэл зай нь нэгээр их оройг нэмдэгт оршино. Дараалалд $d[u] - d[v] > 1$ байх $u$ оршино гэж үзвэл $u$ нь $d[t] \ge d[u] - 1 > d[v]$ байх өөр орой $t$-ээр дамжин дараалалд орсон байх ёстой. Гэвч Дейкстрагийн алгоритм оройнуудыг өсөх дарааллаар тойрдог тул энэ нь боломжгүй.

Энэ нь дарааллын эрэмбэ дараах байдалтай харагдана гэсэн үг:

$$Q = \underbrace{v}_{d[v]}, \dots, \underbrace{u}_{d[v]}, \underbrace{m}_{d[v]+1} \dots \underbrace{n}_{d[v]+1}$$

Энэ бүтэц маш энгийн тул бидэнд жинхэнэ тэргүүлэх эрхийн дараалал хэрэггүй, өөрөөр хэлбэл тэнцвэржүүлсэн хоёртын мод ашиглах нь хэтэрхий их байх болно. Бид зүгээр л энгийн дараалал ашиглаж, харгалзах ирмэг $0$ жинтэй буюу $d[u] = d[v]$ бол шинэ оройг эхэнд, ирмэг $1$ жинтэй буюу $d[u] = d[v] + 1$ бол төгсгөлд залгаж болно. Ингэснээр дараалал үргэлж эрэмбэлэгдсэн хэвээр байна.

vector<int> d(n, INF);
d[s] = 0;
deque<int> q;
q.push_front(s);
while (!q.empty()) {
    int v = q.front();
    q.pop_front();
    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;
        if (d[v] + w < d[u]) {
            d[u] = d[v] + w;
            if (w == 1)
                q.push_back(u);
            else
                q.push_front(u);
        }
    }
}

Диалын алгоритм

Хэрэв бид ирмэгүүдийн жинг бүр илүү том байхыг зөвшөөрвөл бид үүнийг бүр цааш нь өргөтгөж болно. Хэрэв графын ирмэг бүр $\le k$ жинтэй бол дараалал дахь оройнуудын зай нь $v$-ээс эх хүртэлх зайнаас хамгийн ихдээ $k$-аар ялгаатай байна. Тиймээс бид дараалал дахь оройнуудын хувьд $k + 1$ хувин хөтөлж болох ба хамгийн бага зайд харгалзах хувин хоосорох бүрд бид дараагийн илүү өндөр зайтай хувинг авахын тулд циклик шилжилт хийнэ. Энэ өргөтгөлийг Диалын алгоритм гэж нэрлэдэг.

Дасгал бодлогууд