Page 44 - 4387

ЛАБОРАТОРНА РОБОТА № 6

Реалізація алгоритму Данцига пошуку усіх найкоротших

шляхів

6.1 Мета і завдання роботи роботи

Мета роботи – засвоїти принцип пошуку найкоротших

шляхів між усіма вершинами графа за допомогою алгоритму
Данцига.

Завдання роботи – знайти за допомогою алгоритму
Данцига найкоротші шляхи між усіма вершинами заданого графа.

Тривалість лабораторної роботи – 6 год. (3 пари).

6.2 Основні теоретичні положення

Ще один алгоритм пошуку на графі найкоротших шляхів

між усіма парами вершин запропонований американським

математиком Джорджем Данцигом. Алгоритм Данцига досить

близький до алгоритму Флойда-Уоршола та відрізняється від

останнього лише іншим порядком виконання тих самих операцій.

Ідея алгоритму Данцига полягає в наступному. Кожна нова

матриця D , що обчислюється, містить на один рядок і на один

стовпець більше, чим її попередниця, матриця D −1 . Елементи
матриці D , що не входять в останній рядок і стовпець (число

2
таких елементів рівне (m-1) ), визначаються аналогічно, як і в
алгоритмі Флойда-Уоршола. Що ж стосується інших елементів

, де i=m або j=m, то вони визначаються виходячи з наведених

,
нижче міркувань. Найкоротший шлях з вершини i у вершину j

(або навпаки), у якому допускається використання в якості

проміжних тільки перших m вершин графа, не може мати серед

43