Алгоритм Данцига (Glikjnmb :guenig)

Перейти к навигации Перейти к поиску

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

Пронумеровать вершины исходного графа целыми числами от до . Сформировать матрицу (размерностью ), каждый элемент , которой определяет длину кратчайшей дуги ведущей из вершины в вершину . В отсутствие такой дуги положить .

Здесь через обозначается матрица размерностью с элементами . Последовательно определить элементы матрицы из элементов матрицы для принимающих значения :

Кроме того, для всех i и m положить .

Примечания

[править | править код]

Литература

[править | править код]
  • Э. Майника. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 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.