Флойд-Уоршеллийн алгоритм¶

$n$ оройтой чиглэлтэй эсвэл чиглэлгүй жинтэй граф $G$ өгөгдсөн. Даалгавар бол орой $i$ ба $j$ бүрийн хосын хоорондох хамгийн богино замын урт $d_{ij}$-г олох явдал.

Граф сөрөг жинтэй ирмэгтэй байж болох ч сөрөг жинтэй циклгүй.

Хэрэв ийм сөрөг цикл байвал та энэ циклийг дахин дахин тойрч, итерац бүрд замын өртгийг багасгаж болно. Тиймээс та тодорхой замуудыг дурын байдлаар бага болгож болно, өөрөөр хэлбэл тэр хамгийн богино зам тодорхойгүй болно. Энэ нь чиглэлгүй граф сөрөг жинтэй ямар ч ирмэгтэй байж чадахгүй гэдгийг автоматаар илэрхийлнэ, учир нь ийм ирмэгийн дагуу та хүссэн хэрээрээ урагш хойш явж болох тул тэр нь аль хэдийн сөрөг цикл үүсгэдэг.

Энэ алгоритмыг мөн сөрөг цикл байгаа эсэхийг илрүүлэхэд ашиглаж болно. Хэрэв алгоритмын төгсгөлд орой $v$-ээс өөр рүү нь хүрэх зай сөрөг байвал граф сөрөг циклтэй.

Энэ алгоритмыг Роберт Флойд, Стефен Уоршелл нарын өгүүлэлд 1962 онд зэрэг нийтэлсэн. Гэвч 1959 онд Бернард Рой үндсэндээ ижил алгоритмыг нийтэлсэн боловч түүний нийтлэл анзаарагдалгүй өнгөрсөн.

Алгоритмын тайлбар¶

Алгоритмын гол санаа нь дурын хоёр оройн хоорондох хамгийн богино замыг олох процессыг хэд хэдэн дараалсан фаз болгон хуваах явдал юм.

Оройнуудыг 1-ээс $n$ хүртэл дугаарлая. Зайн матриц нь $d[ ][ ]$ юм.

$k$ дахь фазын өмнө ($k = 1 \dots n$) дурын орой $i$ ба $j$-ийн хувьд $d[i][j]$ нь замд зөвхөн $\{1, 2, ..., k-1\}$ оройнуудыг дотоод орой болгон агуулах орой $i$ ба орой $j$-ийн хоорондох хамгийн богино замын уртыг хадгална.

Өөрөөр хэлбэл $k$ дахь фазын өмнө $d[i][j]$-ийн утга нь хэрэв энэ замд зөвхөн $k$-аас бага дугаартай орой руу орохыг зөвшөөрвөл орой $i$-ээс орой $j$ хүрэх хамгийн богино замын урттай тэнцүү (замын эхлэл ба төгсгөл энэ шинжээр хязгаарлагдахгүй).

Энэ шинж эхний фазын хувьд биелдгийг батлахад амархан. $k = 0$-ийн хувьд бид $i$ ба $j$-ийн хооронд $w_{i j}$ жинтэй ирмэг оршин байвал $d[i][j] = w_{i j}$, ирмэг оршихгүй бол $d[i][j] = \infty$ гэж матрицыг дүүргэж болно. Практикт $\infty$ нь ямар нэг өндөр утга байна. Дараа нь бидний харах ёсоор энэ нь алгоритмын шаардлага юм.

Одоо бид $k$ дахь фазад байгаа бөгөөд $(k + 1)$ дэх фазын шаардлагыг хангахаар матриц $d[ ][ ]$-г тооцоолохыг хүсэж байна гэж үзье. Бид зарим оройн хос $(i, j)$-ийн хувьд зайг засах ёстой. Үндсэндээ ялгаатай хоёр тохиолдол бий:

Олонлог $\{1, 2, \dots, k\}$-аас дотоод оройтой, орой $i$-ээс орой $j$ хүрэх хамгийн богино зам нь олонлог $\{1, 2, \dots, k-1\}$-аас дотоод оройтой хамгийн богино замтай давхцана.

Энэ тохиолдолд шилжилтийн үед $d[i][j]$ өөрчлөгдөхгүй.
$\{1, 2, \dots, k\}$-аас дотоод оройтой хамгийн богино зам нь илүү богино.

Энэ нь шинэ, илүү богино зам орой $k$-аар дайран өнгөрнө гэсэн үг. Энэ нь бид $i$ ба $j$-ийн хоорондох хамгийн богино замыг хоёр зам болгон хувааж болно гэсэн үг: $i$ ба $k$-ийн хоорондох зам, мөн $k$ ба $j$-ийн хоорондох зам. Эдгээр хоёр зам хоёулаа зөвхөн $\{1, 2, \dots, k-1\}$-ийн дотоод оройг ашиглах ба тэр утгаараа ийм хамгийн богино замууд байх нь тодорхой. Тиймээс бид эдгээр замын уртыг өмнө нь аль хэдийн тооцоолсон бөгөөд $i$ ба $j$-ийн хоорондох хамгийн богино замын уртыг $d[i][k] + d[k][j]$ гэж тооцоолж болно.

Эдгээр хоёр тохиолдлыг нэгтгэвэл бид $k$ дахь фазад бүх хос $(i, j)$-ийн уртыг дараах байдлаар дахин тооцоолж болохыг олж мэднэ:

$$d_{\text{new}}[i][j] = min(d[i][j], d[i][k] + d[k][j])$$

Тиймээс $k$ дахь фазад шаардагдах бүх ажил бол оройн бүх хосыг давтан үзэж, тэдгээрийн хоорондох хамгийн богино замын уртыг дахин тооцоолох явдал юм. Үр дүнд нь $n$ дэх фазын дараа зайн матриц дахь $d[i][j]$ утга нь $i$ ба $j$-ийн хоорондох хамгийн богино замын урт, эсвэл орой $i$ ба $j$-ийн хооронд зам оршихгүй бол $\infty$ байна.

Сүүлийн тэмдэглэл — бидэнд $k$ дахь фазын хамгийн богино замуудыг түр хадгалахын тулд тусдаа зайн матриц $d_{\text{new}}[ ][ ]$ үүсгэх шаардлагагүй, өөрөөр хэлбэл бүх өөрчлөлтийг аль ч фазад шууд матриц $d[ ][ ]$-д хийж болно. Үнэндээ аль ч $k$ дахь фазад бид зайн матриц дахь дурын замын зайг хамгийн ихдээ сайжруулж байгаа тул $(k+1)$ дэх буюу түүнээс хойшхи фазад боловсруулагдах ямар ч оройн хосын хамгийн богино замын уртыг муутгаж чадахгүй.

Энэ алгоритмын time complexity нь илэрхий байдлаар $O(n^3)$ юм.

Implementation¶

Let $d[][]$ is a 2D array of size $n \times n$, which is filled according to the $0$-th phase as explained earlier. Also we will set $d[i][i] = 0$ for any $i$ at the $0$-th phase.

Then the algorithm is implemented as follows:

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

It is assumed that if there is no edge between any two vertices $i$ and $j$, then the matrix at $d[i][j]$ contains a large number (large enough so that it is greater than the length of any path in this graph). Then this edge will always be unprofitable to take, and the algorithm will work correctly.

However if there are negative weight edges in the graph, special measures have to be taken. Otherwise the resulting values in matrix may be of the form $\infty - 1$, $\infty - 2$, etc., which, of course, still indicates that between the respective vertices doesn't exist a path. Therefore, if the graph has negative weight edges, it is better to write the Floyd-Warshall algorithm in the following way, so that it does not perform transitions using paths that don't exist.

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

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

Дурын өгөгдсөн хоёр оройн хоорондох хамгийн богино замыг оройнуудын дараалал хэлбэрээр сэргээх боломжтой болгох нэмэлт мэдээллийг хөтлөхөд амархан.

Үүний тулд зайн матриц $d[ ][ ]$-ээс гадна өвгүүдийн матриц $p[ ][ ]$-г хөтлөх ёстой бөгөөд энэ нь хоёр оройн хоорондох хамгийн богино зай хамгийн сүүлд өөрчлөгдсөн фазын дугаарыг агуулна. Фазын дугаар нь хайж буй хамгийн богино замын дунд байрлах оройноос өөр юу ч биш гэдэг нь тодорхой. Одоо бид зөвхөн орой $i$ ба $p[i][j]$-ийн хооронд, мөн $p[i][j]$ ба $j$-ийн хоорондох хамгийн богино замыг олох л хэрэгтэй. Энэ нь хамгийн богино замыг сэргээх энгийн рекурсив алгоритмд хүргэнэ.

Бодит жингийн тохиолдол¶

Хэрэв ирмэгийн жин бүхэл биш бодит тоо бол хөвөгч цэгтэй төрөлтэй ажиллахад гардаг алдааг тооцох шаардлагатай.

Флойд-Уоршеллийн алгоритм алдаа маш хурдан хуримтлагддаг тааламжгүй нөлөөтэй. Үнэндээ хэрэв эхний фазад $\delta$ алдаа байвал энэ алдаа хоёр дахь итерацад $2 \delta$, гурав дахь итерацад $4 \delta$ гэх мэтээр тархаж болно.

Үүнээс зайлсхийхийн тулд алгоритмыг дараах харьцуулалтыг ашиглан алдааг (EPS = $\delta$) тооцохоор өөрчилж болно:

if (d[i][k] + d[k][j] < d[i][j] - EPS)
    d[i][j] = d[i][k] + d[k][j];

Сөрөг циклийн тохиолдол¶

Албан ёсоор Флойд-Уоршеллийн алгоритм сөрөг жинтэй цикл агуулсан графт хамаарахгүй. Гэвч $i$-ээс эхэлж, сөрөг циклээр дайран, $j$-д төгсөх зам оршихгүй байх орой $i$ ба $j$-ийн бүх хосын хувьд алгоритм зөв ажилласан хэвээр байна.

Хариу оршихгүй (тэдгээрийн хоорондох замд сөрөг цикл байгаагаас болж) оройн хосын хувьд Флойдын алгоритм зайн матрицад дурын тоо (магадгүй маш сөрөг, гэхдээ заавал биш) хадгална. Гэвч Флойд-Уоршеллийн алгоритмыг ийм оройн хосуудтай болгоомжтой харьцаж, тэдгээрийг жишээ нь $-\text{INF}$ гэж гаргахаар сайжруулах боломжтой.

Үүнийг дараах байдлаар хийж болно: өгөгдсөн графын хувьд ердийн Флойд-Уоршеллийн алгоритмыг ажиллуулъя. Тэгвэл орой $i$ ба $j$-ийн хоорондох хамгийн богино зам нь зөвхөн $i$-ээс хүрч болох ба түүнээс $j$ хүрч болох, $d[t][t] < 0$ байх орой $t$ байх үед л оршихгүй.

Түүнчлэн сөрөг циклтэй графт Флойд-Уоршеллийн алгоритмыг ашиглахдаа зай экспоненциал хурдан сөрөг тал руу орох нөхцөл байдал үүсч болохыг санах хэрэгтэй. Тиймээс хамгийн бага зайг ямар нэг утгаар (жишээ нь $-\text{INF}$) хязгаарлаж бүхэл тооны халилтыг зохицуулах ёстой.

Граф дахь сөрөг циклийг олох тухай дэлгэрэнгүйг Граф дахь сөрөг циклийг олох тусдаа өгүүллээс үзнэ үү.