Пошук найкоротшого шляху

$h : V \to R$ - довільна функція, що відображає вершини на дійсні числа. Для кожного ребра $(u,\;v) \in E$ визначимо

$\hat{\omega}(u,\;v) = \omega(u,\;v) + h(u) - h(v).$

Нехай $p = \langle v_0,\;v_1,\;\ldots,\;v_k \rangle$ - довільний шлях з вершини у вершину . є найкоротшим шляхом з ваговою функцією $\omega$ тоді і тільки тоді, коли він є найкоротшим шляхом з ваговою функцією $\hat{\omega}$ , тобто рівність $\omega(p) = \delta(v_0,\;v_k)$ рівносильно рівності $\hat{\omega}(p) = \hat{\delta}(v_0,\;v_k)$ . Крім того, граф містить цикл з негативним вагою з використанням вагової функції $\omega$ тоді і тільки тоді, коли він містить цикл з негативним вагою з використанням вагової функції $\hat{\omega}$ .

Зміна ваги. Для даного графа створимо новий граф $G' = (V',\;E')$ , де $V' = V \cup \{s\}$ , для деякої нової вершини $s \not\in V$ , а $E' = E \cup \{(s,\;v): v \in V\}$ .

Розширимо вагову функцію $\omega$ таким чином, щоб для всіх вершин $v \in V$ виконувалося рівність $\omega(s,\;v) = 0$ .
Далі визначимо для всіх вершин $v \in V'$ величину $h(v) = \delta(s,\;v)$ і нові ваги для всіх ребер.

Основна процедура. В алгоритмі Джонсона використовується алгоритм Беллмана-Форда і алгоритм Дейкстри, реалізовані у вигляді підпрограм. Ребра зберігаються у вигляді списків суміжних вершин. Алгоритм повертає звичайну матрицю $D = d_{ij}$ розміром $|V|\times |V|$ , де $d_{ij} = \delta(i,\;j)$ , або видає повідомлення про те, що вхідний граф містить цикл з негативною вагою.

Складність. Якщо в алгоритмі Дейкстри неспадними чергу з пріоритетами реалізована у вигляді фібоначчійової купи, то час роботи алгоритму Джонсона дорівнює $O(V^2\log V + V E)$ . При простіший реалізації неубутною черги з пріоритетами час роботи стає рівним $O(V E\log V)$ , але для розріджених графів ця величина в асимптотичному межі веде себе краще, ніж час роботи алгоритму Флойда-Воршелла.

Скачать Содержание