Алгоритм Данцига

Алгоритм Данцига — алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига. Алгоритм близок к алгоритму Флойда, отличается от него только другим порядком исполнения одних и тех же операций.

Алгоритм

Шаг 1

Пронумеровать вершины исходного графа целыми числами от $1$ до $N$. Сформировать матрицу $D_{}^{0}$ (размерностью $N\times N$), каждый элемент $i$, $j$ которой $d_{ij}^{0}$ определяет длину кратчайшей дуги ведущей из вершины $i$ в вершину $j$. В отсутствие такой дуги положить $d_{ij}^{0}=\infty$.

Шаг 2

Здесь через $D_{}^{m}$ обозначается матрица размерностью $m\times m$ с элементами $d_{ij}^{m},m=1,2,...,N$. Последовательно определить элементы матрицы $D^{m}$ из элементов матрицы $D^{m-1}$ для $m$ принимающих значения $1,2,...N$:

$d_{mj}^{m}=min_{i=1,2,...m-1}(d_{mi}^{0}+d_{ij}^{m-1})~(j=1,2,...,m-1)$

$d_{im}^{m}=min_{j=1,2,...m-1}(d_{ij}^{m-1}+d_{jm}^{0})~(i=1,2,...,m-1)$

$d_{ij}^{m}=min(d_{im}^{m}+d_{mj}^{m},d_{ij}^{m-1})~(i,j=1,2,...,m-1)$

Кроме того, для всех i и m положить $d_{ii}^{m}=0$.

См. также

• Алгоритм Флойда — Уоршелла

Литература

• Э. Майника. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 1981. — 324 с.
• De Smith, M.J., Goodchild, M.F. and Longley, P. Geospatial Analysis: A Comprehensive Guide to Principles, Techniques and Software Tools. — Matador, 2007. — 394 p. — ISBN 9781905886609.

Ссылки

• Minieka, Edward. On Computing Sets of Shortest Paths in a Graph (англ.) // Commun. ACM. — ACM, 1974. — Vol. 17, no. 6. — P. 351-353. — ISSN 0001-0782. — doi:10.1145/355616.364037.