Алгоритм Данцига

Проверить информацию. Необходимо проверить точность фактов и достоверность сведений, изложенных в этой статье. На странице обсуждения должны быть пояснения.

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

Алгоритм

Шаг 1

Пронумеровать вершины исходного графа целыми числами от $1$ до $N$. Сформировать матрицу $D_{}^0$ (размерностью $N\times N$), каждый элемент $i$, $j$ которой $d_{ij}^0$ определяет длину кратчайшей дуги ведущей из вершины $i$ в вершину $j$. В отсутствие такой дуги положить $d_{ij}^0 = \infty$.

Шаг 2

Здесь через $D_{}^m$ обозначается матрица размерностью $m\times m$ с элементами $d_{ij}^m, m = 1, 2,..., N$. Последовательно определить элементы матрицы $D^m$ из элементов матрицы $D^{m-1}$ для $m$ принимающих значения $1, 2, ... N$:

$d_{mj}^m = min_{i=1, 2, ... m-1}(d_{mi}^0 + d_{ij}^{m-1})~( j = 1, 2, ..., m-1)$

$d_{im}^m = min_{j=1, 2, ... m-1}(d_{ij}^{m-1} + d_{jm}^{0} )~( i = 1, 2, ..., m-1)$

$d_{ij}^m = min(d_{im}^{m} + d_{mj}^{m} , d_{ij}^{m-1} )~( i, j = 1, 2, ..., m-1)$

Кроме того, для всех i и m положить $d_{ii}^m = 0$.

См. также

• Алгоритм Флойда — Уоршелла

Ссылки

• http://www.spatialanalysisonline.com/output/html/Dantzigalgorithm.html
• «On computing sets of shortest paths in a graph», portal.acm.org  (Проверено 12 апреля 2009)
• Geospatial analysis, Michael John De Smith, Michael F. Goodchild, Paul Longley, Published by Troubador Publishing Ltd, 2006, ISBN 1905886608, ISBN 9781905886609, 394 pages
• Майника Э. Алгоритмы оптимизации на сетях и графах(Мир, 1981)

Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правилами написания статей. Проверить достоверность указанной в статье информации. Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).