Page 37 - 4387
P. 37
0 = 0.
присутня в графі). Для будь-якої вершини i присвоїмо
,
Відзначимо далі, що величина представляє довжину
,
найкоротшого шляху між вершинами i та j.
Позначимо через матрицю розмірністю N×N,
елементами якої є величини . Якщо у вхідному графі відома
,
довжина кожної дуги, то можна сформувати матрицю .
0
В алгоритмі Флойда-Уоршола в якості вхідної виступає
матриця . Спочатку за даною матрицею обчислюється матриця
0
. Потім, за матрицею обчислюється матриця і т.д.
1
2
1
Процес повторюється доти, поки за матрицею −1 не буде
обчислена матриця .
Алгоритм Флойда-Уоршола для знаходження на графі
найкоротших шляхів між усіма парами вершин є таким.
Крок 1. Занумерувати вершини вхідного графа цілими
числами від 1 до N. Визначити матрицю , задавши величину
0
кожного її елемента рівну довжині найкоротшої дуги, що
0
,
з'єднує вершину i з вершиною j. Якщо у вихідному графі
0 = ∞. Крім того,
зазначені вершини не з'єднуються дугами, то
,
0 = 0.
для всіх i=j –
,
Крок 2. Для цілого m, що послідовно набуває значень 1, 2,...,
N, визначити за величинами елементів матриці −1 величини
елементів матриці , використовуючи таке рекурсивне
співвідношення:
d m = min { d m 1 − + d m 1 − ;d m 1 − } . (5.1)
i , j i ,m m , j i , j
При визначенні величини кожного елемента матриці D
фіксувати відповідний найкоротший шлях.
36
