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

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

Алгоритм[ред. | ред. код]

Крок 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}$.

Див. також[ред. | ред. код]

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

Джерело[ред. | ред. код]

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