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

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

Алгоритм

Шаг 1

Пронумеровать вершины исходного графа целыми числами от $1$ до $N$. Сформировать матрицу $D_{}^0$ (размерностью $N\times N$), каждый элемент $i$, $j$ которой $d_{ij}^0$ определяет длину кратчайшей дуги ведущей из вершины $i$ в вершину $j$. В отсутствие такой дуги положить $d_{ij}^0=\mathrm{\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=mi{n}_{i=1,2,...m-1}(d_{mi}^0+d_{ij}^{m-1})(j=1,2,...,m-1)$

$d_{im}^m=mi{n}_{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$.

См. также

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

Литература

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

Ссылки

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