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

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

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

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

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

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

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

Кроме того, для всех i и m положить ${\displaystyle 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.