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

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

Алгоритм

Крок 1

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

Крок 2

Тут через ${\displaystyle D_{}^{m}}$ позначається матриця розмірністю ${\displaystyle mxm}$ з елементами ${\displaystyle d_{ij}^{m},m=1,2,...,N}$. Послідовно визначити елементи матриці ${\displaystyle D^{m}}$ з елементів матриці ${\displaystyle D^{m-1}}$ для ${\displaystyle m}$ що приймають значення ${\displaystyle 1,2,...N}$:

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

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

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

Крім того, для всіх і і m покласти ${\displaystyle d_{ii}^{m}=0}$.

Див. також

Алгоритм Флойда — Воршала

Джерело

Російська Вікіпедія — Алгоритм Данцига