Алгоритм Данцига
Алгоритм Данцига — алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига. Алгоритм близок к алгоритму Флойда, отличается от него только другим порядком исполнения одних и тех же операций.
Алгоритм
Шаг 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.