Page 56 - 4336

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

Позначимо через D матрицю розмірністю N×N,

елементами якої є величини . Якщо у вхідному графі відома
,

довжина кожної дуги, то можна сформувати матрицю D . Ціль

задачі полягає у визначенні матриці D , що представляє
найкоротші шляхи між усіма вершинами вхідного графа.

4.3.1 Алгоритм Флойда-Уоршола

В алгоритмі Флойда-Уоршола в якості вхідної виступає

матриця D . Спочатку за даною матрицею обчислюється матриця

D . Потім, за матрицею D обчислюється матриця D і т.д.
Процес повторюється доти, поки за матрицею D не буде

обчислена матриця D .

Розглянемо основну ідею, що лежить в основі алгоритму

Флойда-Воршелла. Припустимо, що нам відомі:

а) найкоротший шлях з вершини i у вершину m, у якому в

якості проміжних допускається використання тільки перших m-1

вершин;

б) найкоротший шлях з вершини m у вершину j, у якому в

якості проміжних допускається використання тільки перших m-1

вершин;

в) найкоротший шлях з вершини i у вершину j, у якому в

якості проміжних допускається використання тільки перших m-1

вершин.

Оскільки, за припущенням, вхідний граф не може містити

контурів від'ємної довжини, то один із двох шляхів – шлях, що

збігається із представленим у п. “в”, або шлях, що є об'єднанням

шляхів із п. “а” і “б”, – повинен бути найкоротшим шляхом з

56