Найкоротший шлях у графі. Рішення через прямий-двоїстий алгоритм.

Розглянемо добре знайому задачу знаходження найкоротшого шляху. Маючи зв'язний граф $G = (V, E)$, цінову функцію $\omega: E \to R_+$ і дві вершини $s$ і $t$, знайти шлях найменшої вартості, що сполучає ці дві вершини в $G$. Цю задачу можна ефективно розв'язати за допомогою алгоритма Дейкстри. Але тут ми побудуємо прямий-двоїстий алгоритм, що ефективно обчислить найкоротший шлях.

Введемо такі позначення: $\mathcal S = \{ S \mid S \subset V, s \in S, t \notin S\}$ і, для кожної множини $S \subset V$, через $\delta(S)$ позначимо множину ребер, що мають одну вешину в $S$, а другу в $V\setminus S$.

Для цього ми роглянемо лінійну програму в формі. Взагалі-то, нам потрібно, щоб $x_e$ набували лише ${0,1}$, але цілочисельні лінійні програми NP-складні, тому ми ослаблюємо програму до нецілочельної лінійної програми. $$\begin{align} \min \sum_{e\in E}x_e\cdot\omega(e) \end{align}$$ за умови, що $$\begin{align} \forall S \in \mathcal{S}, \sum_{e\in \delta(S)} x_e\ge 1\\ \forall e \in E, x_e \ge 0 \end{align}$$ Наступний крок - це створення двоїстої лінійної програми. Для того, щоб це зробити спочатку згадаємо як виглядає лінійна програма в стандартній формі: $$\begin{align*} &\max \sum_{j=1}^n c_j x_j\\ \text{за умови, що}&\sum_{j=1}^n a_{ij}x_j \le b_i, i = 1,2,\dots, m\\ &x_j \ge 0, j = 1,2, \dots, n \end{align*}$$ Часто зручніше записувати в матричному вигляді: $$\begin{align*} &\max c^Tx\\ \text{за умови, що}&\ Ax \le b, x \ge 0 \end{align*}$$ Тоді двоїста програма така: $$\begin{align*} &\min b^T y\\ \text{за умови, що}&\ A^Ty \ge c, y \ge 0 \end{align*}$$ Тепер ми можемо записати двоїсту програму:

$$\begin{align} \max \sum_{S\in\mathcal{S}}y_S \end{align}$$ за умови, що $$\begin{align} \sum_{S:e\in \delta(S)} y_S\le c_e, \forall e \in E \label{eq:dual_constraint}\\ \forall S \in \mathcal{S}, y_S \ge 0 \end{align}$$ Тобто, тепер ми максимізуємо суму нових зміних $y_S$. У ($\ref{eq:dual_constraint}$) ми для кожного ребра, сумуємо $y_S$ з усіх $S$, що перетинають це ребро.

Алгоритм

Роглянемо такий алгоритм:

1. $F\gets \varnothing$
2. $y \gets 0$
3. Допоки в $F$ ще нема шляху, що поєднує $s$ і $t$
• Нехай $C$ - компонента зв'язності графу $G' = (V, F)$, що містить $s$
• Збільшити двоїсту змінну $y_C$ так, щоб вперше виконалось $\sum\limits_{S \in \mathcal{S}~:~e \in \delta(S)} y_S = w(e')$
• Додати $e'$ до $F$
4. Повернути шлях $P$ з $F$, що поєднує $s$ і $t$.

Коректність

На кожній ітерації ми збільшуємо іншу $y_S$, бо $C$ постійно змінюється. Отже виконання алгоритму завершиться не пізніше ніж через $|V|$ кроків.

Перебіг виконання

Спочатку сформулюємо лему, яка нам допоможе зрозуміти як виконується алгоритм.

Лема

На кожному кроці алгоритму множина $F$ - це дерево.

Важливо, що ми повертаємо не все дерево, а лише шлях, що поєднує дві вершини. Читач може переконатись, що порядок додавання ребер в дереву той самий, що й у алгоритму Дейкстри.