Page 36 - 4387

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

Реалізація алгоритму Флойда-Уоршола пошуку усіх

найкоротших шляхів

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

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

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

Завдання роботи – знайти за допомогою алгоритму
Флойда-Уоршола найкоротші шляхи між усіма вершинами

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

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

Алгоритм Флойда-Уоршола дозволяє знаходити

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

графа. В даному алгоритмі для довжин дуг допускаються від'ємні

значення, однак не допускається наявність контурів від'ємні

довжини.

Занумеруємо вершини вхідного графа цілими числами від 1

до N. Позначимо через довжину найкоротшого шляху з

,
вершини i у вершину j, який у якості проміжних може містити
тільки перші m вершин графа. Якщо між вершинами i та j не

існує жодного шляху зазначеного типу, то умовно будемо

= ∞. З даного визначення величин випливає,
вважати, що
, ,
що величина представляє довжину найкоротшого шляху з
0
,
вершини i у вершину j, що не має проміжних вершин, тобто
довжину найкоротшої дуги, що з'єднує i з j (якщо така дуга

35