Кількість шляхів фіксованої довжини / Найкоротші шляхи фіксованої довжини

Ця стаття описує розв'язки двох задач, що ґрунтуються на одній і тій самій ідеї: звести задачу до побудови матриці й обчислити відповідь за допомогою звичайного множення матриць або його модифікованого варіанта.

Коли підходить цей алгоритм?

• Довжина шляху $k$ задана й фіксована (часто велика), а потрібна кількість або мінімальна вага шляхів рівно з $k$ ребер? (якщо $k$ не фіксоване, а потрібен звичайний найкоротший шлях → Дейкстра / Беллман-Форд)
• Кількість вершин $n$ мала, щоб витримати $O(n^3 \log k)$ через бінарне піднесення матриці до степеня?
• Шляхи можуть бути непростими (вершини й ребра дозволено повторювати)?

Кількість шляхів фіксованої довжини

Нам задано орієнтований незважений граф $G$ із $n$ вершинами, а також ціле число $k$. Задача така: для кожної пари вершин $(i, j)$ потрібно знайти кількість шляхів довжини $k$ між цими вершинами. Шляхи не обов'язково прості, тобто вершини та ребра можна відвідувати будь-яку кількість разів у межах одного шляху.

Вважаємо, що граф задано матрицею суміжності, тобто матрицею $G[][]$ розміру $n \times n$, де кожен елемент $G[i][j]$ дорівнює $1$, якщо вершина $i$ з'єднана з $j$ ребром, і $0$, якщо вони ребром не з'єднані. Наведений алгоритм працює також у випадку кратних ребер: якщо деяка пара вершин $(i, j)$ з'єднана $m$ ребрами, то це можна записати в матриці суміжності, поклавши $G[i][j] = m$. Також алгоритм працює, якщо граф містить петлі (петля — це ребро, що з'єднує вершину саму із собою).

Очевидно, що побудована матриця суміжності і є відповіддю на задачу для випадку $k = 1$. Вона містить кількість шляхів довжини $1$ між кожною парою вершин.

Будуватимемо розв'язок ітеративно: припустимо, що ми знаємо відповідь для деякого $k$. Тут ми опишемо, як можна побудувати відповідь для $k + 1$. Позначимо через $C_k$ матрицю для випадку $k$, а через $C_{k+1}$ — матрицю, яку ми хочемо побудувати. За допомогою такої формули ми можемо обчислити кожен елемент $C_{k+1}$:

$$C_{k+1}[i][j] = \sum_{p = 1}^{n} C_k[i][p] \cdot G[p][j]$$

Легко бачити, що ця формула обчислює не що інше, як добуток матриць $C_k$ і $G$:

$$C_{k+1} = C_k \cdot G$$

Отже, розв'язок задачі можна подати так:

$$C_k = \underbrace{G \cdot G \cdots G}_{k \text{ times}} = G^k$$

Залишається зауважити, що добутки матриць можна ефективно підносити до високого степеня за допомогою бінарного піднесення до степеня. Це дає розв'язок зі складністю $O(n^3 \log k)$.

Найкоротші шляхи фіксованої довжини

Нам задано орієнтований зважений граф $G$ із $n$ вершинами та ціле число $k$. Для кожної пари вершин $(i, j)$ потрібно знайти довжину найкоротшого шляху між $i$ та $j$, що складається рівно з $k$ ребер.

Вважаємо, що граф задано матрицею суміжності, тобто матрицею $G[][]$ розміру $n \times n$, де кожен елемент $G[i][j]$ містить довжину ребра від вершини $i$ до вершини $j$. Якщо ребра між двома вершинами немає, то відповідному елементу матриці присвоюється нескінченність $\infty$.

Очевидно, що в такому вигляді матриця суміжності і є відповіддю на задачу для $k = 1$. Вона містить довжини найкоротших шляхів між кожною парою вершин або $\infty$, якщо шляху з одного ребра не існує.

І знову ми можемо будувати розв'язок задачі ітеративно: припустимо, що ми знаємо відповідь для деякого $k$. Покажемо, як можна обчислити відповідь для $k+1$. Позначимо через $L_k$ матрицю для $k$, а через $L_{k+1}$ — матрицю, яку ми хочемо побудувати. Тоді така формула обчислює кожен елемент $L_{k+1}$:

$$L_{k+1}[i][j] = \min_{p = 1 \ldots n} \left(L_k[i][p] + G[p][j]\right)$$

Придивившись до цієї формули уважніше, можемо провести аналогію з множенням матриць: насправді матриця $L_k$ множиться на матрицю $G$, з єдиною відмінністю — в операції множення ми беремо мінімум замість суми, а суму як внутрішню операцію замість множення.

$$L_{k+1} = L_k \odot G,$$

де операцію $\odot$ означено так:

$$A \odot B = C~~\Longleftrightarrow~~C_{i j} = \min_{p = 1 \ldots n}\left(A_{i p} + B_{p j}\right)$$

Таким чином, розв'язок задачі можна подати за допомогою модифікованого множення:

$$L_k = \underbrace{G \odot \ldots \odot G}_{k~\text{times}} = G^{\odot k}$$

Залишається зауважити, що це піднесення до степеня ми так само можемо обчислити ефективно за допомогою бінарного піднесення до степеня, оскільки модифіковане множення, очевидно, асоціативне. Отже, цей розв'язок теж має складність $O(n^3 \log k)$.

Узагальнення задач для шляхів довжини щонайбільше $k$

Наведені вище розв'язки розв'язують задачі для фіксованого $k$. Однак їх можна пристосувати для розв'язання задач, у яких шляхам дозволено містити не більш ніж $k$ ребер.

Це можна зробити, дещо змінивши вхідний граф.

Ми дублюємо кожну вершину: для кожної вершини $v$ ми створюємо ще одну вершину $v'$ та додаємо ребро $(v, v')$ і петлю $(v', v')$. Кількість шляхів між $i$ та $j$ з не більш ніж $k$ ребрами дорівнює кількості шляхів між $i$ та $j'$ рівно з $k + 1$ ребрами, оскільки існує бієкція, яка зіставляє кожному шляху $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j]$ довжини $m \le k$ шлях $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j, j', \ldots, j']$ довжини $k + 1$.

Той самий прийом можна застосувати для обчислення найкоротших шляхів із не більш ніж $k$ ребрами. Ми знову дублюємо кожну вершину й додаємо два згадані ребра з вагою $0$.