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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Крок 1[ред. | ред. код]

Пронумерувати вершини вихідного графа цілими числами від до . Сформувати матрицю (розмірністю ), кожен елемент , якої визначає довжину найкоротшої дуги яка веде з вершини у вершину . В разі відсутності такої дуги покласти .

Крок 2[ред. | ред. код]

Тут через позначається матриця розмірністю з елементами . Послідовно визначити елементи матриці з елементів матриці для що приймають значення :

Крім того, для всіх і і m покласти .

Дивіться також[ред. | ред. код]

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

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

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