Алгоритмы на графах
Алгоритм Дейкстры
Постановка задачи
$G = (V, E)$ – граф, $E \subset V \times V$, $\rho \colon E \to \mathbb R$ – весовая функция рёбер, $\rho \geq 0$, $s \in V$ – заданная вершина графа.
Путь из $s$ в $u \in V$ – это последовательность \(\{v_i\}_{i=0}^K \subset V\) такая, что \(v_0 = s\), \(v_K = u\), \((v_i, v_{i+1}) \in E\), \(i = \overline{0, K-1}\).
Обозначим через \(d_*(u)\) длину кратчайшего пути из $s$ в $u$: \(d_*(u) = \min\limits_{\{v_i\}} \sum\limits_{i=0}^{K-1} \rho(v_i, v_{i+1}).\)
Требуется найти \(d_*(u)\) для всех $u \in V$, а также сами кратчайшие пути из $s$ до всех остальных вершин графа.
Алгоритм
$F \subset V$ – множество вершин, путь до которых вычислен
$d(v)$, $v \in V$ – текущая длина пути
$F \leftarrow \varnothing$; $d(v) \leftarrow \infty \, \forall v \in V$; $d(s) \leftarrow 0$;
for \(i \leftarrow 1\) to \(|V|\)
\(u \leftarrow \mathop{\mathrm{arg\,min}}\limits_{v \in V \setminus F} d(v)\);
\(F \leftarrow F \cup \{u\}\);
for \(\{v \colon (u, v) \in E\}\)
\(d(v) \leftarrow \min \{d(v), d(u) + \rho(u, v)\}\);
endfor
endfor
Обоснование алгоритма
Теорема. Инвариант цикла: \(d(v) = d_*(v) \; \forall v \in F\).
Доказательство.
На каждой итерации $d(v)$ равно длине кратчайшего пути от $s$ до $v$, проходящего через вершины множества $F$. Теорема утверждает, что для вершины $u$ из $V\setminus F$ с минимальным значением $d(v)$ кратчайший путь из $s$ лежит через вершины множества $F$. Предположим противное: существует кратчайший путь \(\{v_i\}\) из $s$ в $u$ такой, что его длина \(d_*(u)\) меньше $d(u)$, причем \(v_j \notin F\). Заметим, что \(d(v_j) = d_*(v_j)\), поскольку кратчайший путь из $s$ в \(v_j\) проходит через вершины множества $F$. Также заметим, что \(d_*(v_j) \leq d_*(u)\), поскольку веса ребер неотрицательны. Таким образом, \(d(v_j) = d_*(v_j) \leq d_*(u) < d(u)\). Итак, \(d(v_j) < d(u)\) и \(v_j \in V\setminus F\), что противоречит выбору вершины \(u\).