Обход графов

Кратчайший путь в сети пунктов

Пусть $V$ – множество пунктов, $E \subset V \times V$ – множество дорог между пунктами, $a,b \in V$ – два пункта. Требуется найти путь из пункта $a$ в пункт $b$, длина которого минимальна.

Для решения этой задачи эффективен поиск в ширину (см. [Ахо, с. 218], [Луридас, с. 76], [КЛРШ, с. 630]).

Идея поиска в ширину заключается в построении множеств пунктов, длина кратчайшего пути до которых равна $0, 1, 2, 3, \ldots$

Обозначим через $V_k$ множество вершин, в которые идут дороги из множества $V_{k-1}$ (за исключением вершин, принадлежащих одному из множеств $V_i$, $i < k$), при этом $V_0 = {a}$. Легко проверить, что для пунктов $v \in V_k$ длина кратчайшего пути из $a$ в $v$ равна $k$.

Алгоритм производит обработку пунктов из множества $V_0$, затем множества $V_1$, множества $V_2$ и т.д. На $k$-м этапе выполнения алгоритма перебираются все вершины множества $V_{k-1}$, и для каждой из них перебираются все исходящие дороги. Если дорога ведет в не просмотренный ранее пункт, то этот пункт добавляется к множеству $V_k$. Для каждого пункта $v \in V_k$ алгоритм запоминает пункт $u \in V_{k-1}$, из которого был произведен переход в пункт $v$.

Обозначим: $d[v]$ – найденная длина кратчайшего пути из $a$ в $v$, $p[v]$ – предшествующая вершина в кратчайшем пути из $a$ в $v$, \({\rm adj\_points}(v) = \{u \in V \colon (v, u) \in E\}\), $n = |V|$ – число пунктов, $m = |E|$ – число дорог.

${\tt \ 1}\;$ $d[v] \leftarrow \infty,\; p[v] \leftarrow \Lambda \;\, \forall v \in V$
${\tt \ 2}\;$ $V_0 \leftarrow {a}$
${\tt \ 3}\;$ \({\bf for}\;\; k \leftarrow 1\, .\,. \,n-1 \;\; \{\)
${\tt \ 4}\;\qquad$ $V_k \leftarrow \varnothing$
${\tt \ 5}\;\qquad$ \({\bf for}\;\; v \in V_{k-1} \;\; \{\)
${\tt \ 6}\;\qquad\qquad$ \({\bf for}\;\; u \in {\rm adj\_points}(v) \;\; \{\)
${\tt \ 7}\;\qquad\qquad\qquad$ \({\bf if}\;\; d[u] = \infty \;\; \{\)
${\tt \ 8}\;\qquad\qquad\qquad\qquad$ $V_k \leftarrow V_k \cup {u}$
${\tt \ 9}\;\qquad\qquad\qquad\qquad$ $d[u] \leftarrow k$
${\tt 10}\;\qquad\qquad\qquad\qquad$ $p[u] \leftarrow v$
${\tt 11}\;\qquad\qquad\qquad$ \(\}\)
${\tt 12}\;\qquad\qquad$ \(\}\)
${\tt 13}\;\qquad$ \(\}\)
${\tt 14}\;$ \(\}\)

Каждый пункт и каждая дорога будет обработана по одному разу, поэтому временная сложность алгоритма $O(n + m)$.

Спрашивается: как хранить множества $V_k$? Первый способ – реализовать каждое множество в виде списка. Для этого потребуется $O(n)$ дополнительной памяти, что приемлемо. Второй способ – не выделять отдельно множества $V_k$, а складывать вершины, подлежащие обработке, в СД “очередь”.

Задача коммивояжера

Задача коммивояжера [Ахо, с. 290] состоит в нахождении замкнутого пути с минимальным весом. Здесь каждой дороге приписан вес $\rho(u, v) \geq 0$, $(u,v) \in E$.

Переборный алгоритм с временной сложностью $O(n!)$ сводится к алгоритму генерации перестановок длины $n$.

Литература

[КЛРШ] Кормен, Лейзерсон, Ривест, Штайн – Алгоритмы: Построение и анализ (2013)

[Ахо] Ахо, Хопкрофт, Ульман – Структуры данных и алгоритмы (2000)

[Луридас] Луридас – Алгоритмы для начинающих. Теория и практика для разработчика (2018)

[Касьянов] Касьянов, Евстигнеев – Графы в программировании: обработка, визуализация и применение (2003)