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

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

Алгоритм

Шаг 1

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

Шаг 2

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

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

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

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

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

См. также

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

Литература

• Э. Майника. Алгоритмы оптимизации на сетях и графах. — М.: Мир, 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 [www.sigla.ru/table.jsp?f=8&t=3&v0=0001-0782&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0001-0782]. — DOI:10.1145/355616.364037.

Отрывок, характеризующий Алгоритм Данцига

В ту минуту как кавалергарды, миновав его, скрылись в дыму, Ростов колебался, скакать ли ему за ними или ехать туда, куда ему нужно было. Это была та блестящая атака кавалергардов, которой удивлялись сами французы. Ростову страшно было слышать потом, что из всей этой массы огромных красавцев людей, из всех этих блестящих, на тысячных лошадях, богачей юношей, офицеров и юнкеров, проскакавших мимо его, после атаки осталось только осьмнадцать человек.
«Что мне завидовать, мое не уйдет, и я сейчас, может быть, увижу государя!» подумал Ростов и поскакал дальше.
Поровнявшись с гвардейской пехотой, он заметил, что чрез нее и около нее летали ядры, не столько потому, что он слышал звук ядер, сколько потому, что на лицах солдат он увидал беспокойство и на лицах офицеров – неестественную, воинственную торжественность.
Проезжая позади одной из линий пехотных гвардейских полков, он услыхал голос, назвавший его по имени.
– Ростов!
– Что? – откликнулся он, не узнавая Бориса.
– Каково? в первую линию попали! Наш полк в атаку ходил! – сказал Борис, улыбаясь той счастливой улыбкой, которая бывает у молодых людей, в первый раз побывавших в огне.
Ростов остановился.
– Вот как! – сказал он. – Ну что?
– Отбили! – оживленно сказал Борис, сделавшийся болтливым. – Ты можешь себе представить?
И Борис стал рассказывать, каким образом гвардия, ставши на место и увидав перед собой войска, приняла их за австрийцев и вдруг по ядрам, пущенным из этих войск, узнала, что она в первой линии, и неожиданно должна была вступить в дело. Ростов, не дослушав Бориса, тронул свою лошадь.
– Ты куда? – спросил Борис.
– К его величеству с поручением.
– Вот он! – сказал Борис, которому послышалось, что Ростову нужно было его высочество, вместо его величества.
И он указал ему на великого князя, который в ста шагах от них, в каске и в кавалергардском колете, с своими поднятыми плечами и нахмуренными бровями, что то кричал австрийскому белому и бледному офицеру.