Дейкстрагийн алгоритм¶

Бидэнд $n$ орой, $m$ ирмэгтэй чиглэлтэй эсвэл чиглэлгүй жинтэй граф өгөгдсөн. Бүх ирмэгийн жин сөрөг биш. Мөн эхлэлийн орой $s$ өгөгдсөн. Энэ өгүүлэлд эхлэлийн орой $s$-ээс бусад бүх орой хүрэх хамгийн богино замын уртыг олох, мөн хамгийн богино замуудыг өөрсдийг нь гаргах тухай авч үзнэ.

Энэ бодлогыг мөн ганц эхээс гарах хамгийн богино замын бодлого гэж нэрлэдэг.

Алгоритм¶

Голланд компьютерын эрдэмтэн Эдсгер В. Дейкстрагийн 1959 онд тайлбарласан алгоритм энд байна.

Орой $v$ бүрийн хувьд $s$-ээс $v$ хүрэх хамгийн богино замын одоогийн уртыг $d[v]$-д хадгалах массив $d[]$ үүсгэе. Эхэндээ $d[s] = 0$ бөгөөд бусад бүх оройн хувьд энэ урт хязгааргүйтэй тэнцүү. Хэрэгжүүлэлтэд хязгааргүй болгож хангалттай том тоог (боломжит дурын замын уртаас их байх нь баталгаатай тоог) сонгодог.

$$d[v] = \infty,~ v \ne s$$

Түүнчлэн бид орой $v$ бүрийн хувьд түүнийг тэмдэглэсэн эсэхийг хадгалах Булын массив $u[]$ хөтөлнө. Эхэндээ бүх орой тэмдэглэгдээгүй байна:

$$u[v] = {\rm false}$$

Дейкстрагийн алгоритм $n$ итерац ажиллана. Итерац бүрд $d[v]$ хамгийн бага утгатай тэмдэглэгдээгүй орой $v$-г сонгоно:

Эхний итерацад эхлэлийн орой $s$ сонгогдох нь илэрхий.

Сонгогдсон орой $v$-г тэмдэглэнэ. Дараа нь орой $v$-ээс сулруулалт гүйцэтгэнэ: $(v,\text{to})$ хэлбэрийн бүх ирмэгийг авч үзэх ба орой $\text{to}$ бүрийн хувьд алгоритм $d[\text{to}]$ утгыг сайжруулахыг оролдоно. Хэрэв одоогийн ирмэгийн урт $len$-тэй тэнцүү бол сулруулалтын код нь:

$$d[\text{to}] = \min (d[\text{to}], d[v] + len)$$

Ийм бүх ирмэгийг авч үзсэний дараа одоогийн итерац дуусна. Эцэст нь $n$ итерацын дараа бүх орой тэмдэглэгдэх ба алгоритм дуусна. Олдсон утгууд $d[v]$ нь $s$-ээс бүх орой $v$ хүрэх хамгийн богино замын урт болно гэж бид батлан хэлнэ.

Хэрэв зарим орой эхлэлийн орой $s$-ээс хүрэх боломжгүй бол тэдгээрийн $d[v]$ утга хязгааргүй хэвээр үлдэхийг анзаар. Алгоритмын сүүлийн хэдэн итерац тэдгээр оройг сонгох нь илэрхий боловч тэдэнд ямар ч ашигтай ажил хийгдэхгүй. Тиймээс сонгогдсон орой хүртэлх зай хязгааргүй болмогц алгоритмыг зогсоож болно.

Хамгийн богино замыг сэргээх¶

Ихэвчлэн зөвхөн хамгийн богино замын уртыг төдийгүй хамгийн богино замуудыг өөрсдийг нь мэдэх шаардлагатай байдаг. $s$-ээс дурын орой хүрэх хамгийн богино замыг сэргээхэд хангалттай мэдээллийг хэрхэн хөтлөхийг үзье. Бид орой $v \ne s$ бүрийн хувьд $p[v]$ нь $s$-ээс $v$ хүрэх хамгийн богино зам дахь сүүлээсээ хоёр дахь орой байх өмнөх оройнуудын массив $p[]$ хөтөлнө. Энд бид ямар нэг орой $v$ хүрэх хамгийн богино замыг аваад тэр замаас $v$-г хасвал орой $p[v]$-д төгсөх зам гарах ба энэ зам нь орой $p[v]$-ийн хувьд хамгийн богино байх болно гэдэг баримтыг ашиглаж байна. Өмнөх оройнуудын энэ массивыг ашиглан дурын орой хүрэх хамгийн богино замыг сэргээж болно: $v$-ээс эхлэн эхлэлийн орой $s$ хүрэх хүртэл одоогийн оройн өмнөх оройг давтан авснаар оройнууд нь урвуу дарааллаар жагссан шаардлагатай хамгийн богино замыг авна. Тэгэхээр орой $v$ хүрэх хамгийн богино зам $P$ нь:

$$P = (s, \ldots, p[p[p[v]]], p[p[v]], p[v], v)$$

Өмнөх оройнуудын энэ массивыг байгуулах нь маш энгийн: амжилттай сулруулалт бүрд, өөрөөр хэлбэл сонгогдсон ямар нэг орой $v$-ийн хувьд ямар нэг орой $\text{to}$ хүрэх зайд сайжруулалт гарах үед бид $\text{to}$-ийн өмнөх оройг орой $v$-ээр шинэчилнэ:

$$p[\text{to}] = v$$

Баталгаа¶

Дейкстрагийн алгоритмын зөв байдал үндэслэж буй үндсэн мэдэгдэл нь дараах юм:

Дурын орой $v$ тэмдэглэгдсэний дараа түүн хүрэх одоогийн зай $d[v]$ нь хамгийн богино байх ба цаашид өөрчлөгдөхгүй.

Баталгааг индукцээр хийнэ. Эхний итерацын хувьд энэ мэдэгдэл илэрхий: тэмдэглэгдсэн цорын ганц орой нь $s$ бөгөөд түүн хүрэх зай $d[s] = 0$ нь үнэхээр $s$ хүрэх хамгийн богино замын урт юм. Одоо энэ мэдэгдэл өмнөх бүх итерацын хувьд, өөрөөр хэлбэл аль хэдийн тэмдэглэгдсэн бүх оройн хувьд үнэн гэж үзье; одоогийн итерац дууссаны дараа энэ зөрчигдөхгүйг батлая. $v$ нь одоогийн итерацад сонгогдсон орой, өөрөөр хэлбэл $v$ нь алгоритмын тэмдэглэх орой байг. Одоо бид $d[v]$ нь үнэхээр түүн хүрэх хамгийн богино замын урт $l[v]$-тэй тэнцүү болохыг батлах ёстой.

Орой $v$ хүрэх хамгийн богино зам $P$-г авч үзье. Энэ замыг хоёр хэсэгт хувааж болно: зөвхөн тэмдэглэгдсэн зангилаанаас тогтох $P_1$ (дор хаяж эхлэлийн орой $s$ нь $P_1$-ийн хэсэг байна), мөн замын үлдсэн хэсэг $P_2$ (энэ нь тэмдэглэгдсэн орой агуулж болох боловч үргэлж тэмдэглэгдээгүй оройгоор эхэлнэ). Зам $P_2$-ийн эхний оройг $p$, зам $P_1$-ийн сүүлийн оройг $q$ гэж тэмдэглэе.

Эхлээд бид орой $p$-ийн хувьд мэдэгдлээ батална, өөрөөр хэлбэл $d[p] = l[p]$ болохыг батлая. Энэ нь бараг илэрхий: өмнөх итерацуудын нэгэнд бид орой $q$-г сонгож, түүнээс сулруулалт гүйцэтгэсэн. (Орой $p$-г сонгосны ачаар) $p$ хүрэх хамгийн богино зам нь $q$ хүрэх хамгийн богино зам дээр нэмээд ирмэг $(p,q)$ тул $q$-ээс хийсэн сулруулалт $d[p]$-ийн утгыг хамгийн богино замын урт $l[p]$ болгож тохируулсан.

Ирмэгүүдийн жин сөрөг биш тул хамгийн богино замын урт $l[p]$ (бидний дөнгөж сая $d[p]$-тэй тэнцүү гэж баталсан) нь орой $v$ хүрэх хамгийн богино замын урт $l[v]$-ээс хэтрэхгүй. $l[v] \le d[v]$ болохыг харгалзвал (учир нь Дейкстрагийн алгоритм боломжит хамгийн богиноос богино замыг олж чадахгүй) бид дараах тэнцэтгэл бишийг авна:

$$d[p] = l[p] \le l[v] \le d[v]$$

Нөгөө талаас орой $p$ ба $v$ хоёул тэмдэглэгдээгүй бөгөөд одоогийн итерац $p$ биш орой $v$-г сонгосон тул бид өөр нэг тэнцэтгэл биш авна:

$$d[p] \ge d[v]$$

Эдгээр хоёр тэнцэтгэл бишээс бид $d[p] = d[v]$ гэж дүгнэх ба дараа нь өмнө олсон тэнцэтгэлүүдээс дараахыг авна:

$$d[v] = l[v]$$

Баталгаа дууслаа.

Implementation¶

Dijkstra's algorithm performs $n$ iterations. On each iteration it selects an unmarked vertex $v$ with the lowest value $d[v]$, marks it and checks all the edges $(v, \text{to})$ attempting to improve the value $d[\text{to}]$.

The running time of the algorithm consists of:

$n$ searches for a vertex with the smallest value $d[v]$ among $O(n)$ unmarked vertices
$m$ relaxation attempts

For the simplest implementation of these operations on each iteration vertex search requires $O(n)$ operations, and each relaxation can be performed in $O(1)$. Hence, the resulting asymptotic behavior of the algorithm is:

$$O(n^2+m)$$

This complexity is optimal for dense graph, i.e. when $m \approx n^2$. However in sparse graphs, when $m$ is much smaller than the maximal number of edges $n^2$, the problem can be solved in $O(n \log n + m)$ complexity. The algorithm and implementation can be found on the article Dijkstra on sparse graphs.

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);
    vector<bool> u(n, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }

        if (d[v] == INF)
            break;

        u[v] = true;
        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;
            }
        }
    }
}

Here the graph $\text{adj}$ is stored as adjacency list: for each vertex $v$ $\text{adj}[v]$ contains the list of edges going from this vertex, i.e. the list of pair<int,int> where the first element in the pair is the vertex at the other end of the edge, and the second element is the edge weight.

The function takes the starting vertex $s$ and two vectors that will be used as return values.

First of all, the code initializes arrays: distances $d[]$, labels $u[]$ and predecessors $p[]$. Then it performs $n$ iterations. At each iteration the vertex $v$ is selected which has the smallest distance $d[v]$ among all the unmarked vertices. If the distance to selected vertex $v$ is equal to infinity, the algorithm stops. Otherwise the vertex is marked, and all the edges going out from this vertex are checked. If relaxation along the edge is possible (i.e. distance $d[\text{to}]$ can be improved), the distance $d[\text{to}]$ and predecessor $p[\text{to}]$ are updated.

After performing all the iterations array $d[]$ stores the lengths of the shortest paths to all vertices, and array $p[]$ stores the predecessors of all vertices (except starting vertex $s$). The path to any vertex $t$ can be restored in the following way:

vector<int> restore_path(int s, int t, vector<int> const& p) {
    vector<int> path;

    for (int v = t; v != s; v = p[v])
        path.push_back(v);
    path.push_back(s);

    reverse(path.begin(), path.end());
    return path;
}

Эх сурвалж¶

Edsger Dijkstra. A note on two problems in connexion with graphs [1959]
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005]