WikiSort.ru - Программирование

о проекте

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

Алгоритм

Шаг 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.

    Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

    Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

    Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




    Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

    Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

    2019-2019
    WikiSort.ru - проект по пересортировке и дополнению контента Википедии