Алгоритм Данцига — алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига. Алгоритм близок к алгоритму Флойда, отличается от него только другим порядком исполнения одних и тех же операций.
Алгоритм
Шаг 1 Пронумеровать вершины исходного графа целыми числами от до . Сформировать матрицу (размерностью ), каждый элемент , которой определяет длину кратчайшей дуги ведущей из вершины в вершину . В отсутствие такой дуги положить .
Шаг 2 Здесь через обозначается матрица размерностью с элементами . Последовательно определить элементы матрицы из элементов матрицы для принимающих значения :
Кроме того, для всех i и m положить .
См. также Алгоритм Флойда — Уоршелла
Примечания
Литература
Ссылки
Флойда—Уоршелла Категория:Динамическое программирование