Алгоритм Данцига
Перейти к навигации
Перейти к поиску
Проверить информацию. |
Алгоритм Данцига — алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига. Алгоритм близок к алгоритму Флойда, отличается от него только другим порядком исполнения одних и тех же операций.
Алгоритм[править | править код]
Шаг 1[править | править код]
Пронумеровать вершины исходного графа целыми числами от до . Сформировать матрицу (размерностью ), каждый элемент , которой определяет длину кратчайшей дуги ведущей из вершины в вершину . В отсутствие такой дуги положить .
Шаг 2[править | править код]
Здесь через обозначается матрица размерностью с элементами . Последовательно определить элементы матрицы из элементов матрицы для принимающих значения :
Кроме того, для всех 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.
Для улучшения этой статьи желательно:
|