Русская Википедия:Алгоритм Данцига

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Алгоритм

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:Статья