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

Алгоритм

Шаг 1

Пронумеровать вершины исходного графа целыми числами от ${\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 }$ .

Шаг 2

Здесь через ${\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 . — doi : .

Для улучшения этой статьи желательно : Переработать оформление в соответствии с правилами написания статей . Проверить достоверность указанной в статье информации. На должны быть пояснения. Дополнить статью (статья слишком короткая либо содержит лишь словарное определение ). После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.