Page 57 - 4336

вершини i у вершину j, у якому в якості проміжних допускається

використання тільки перших m вершин. Таким чином,

m
d i m  min  d i m 1   d m , j 1  ;d i m 1  . (4.2)
, j
,m
, j
Із співвідношення (4.2) видно, що для обчислення елементів

матриці D необхідно мати лише елементами матриці D .
Більше того, відповідні обчислення можуть бути проведені без

звертання до вхідного графа.

Алгоритм Флойда-Уоршола для знаходження на графі

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

наступним чином.

Крок 1. Занумерувати вершини вхідного графа цілими

числами від 1 до N. Визначити матрицю D , задавши величину

кожного її елемента рівну довжині найкоротшої дуги, що
,
з'єднує вершину i з вершиною j. Якщо у вихідному графі

зазначені вершини не з'єднуються дугами, то ∞. Крім того,
,
для всіх i=j – 0.
,

Крок 2. Для цілого m, що послідовно набуває значень 1, 2,...,

N, визначити за величинами елементів матриці D величини

елементів матриці D , використовуючи рекурсивне
співвідношення (4.2). При визначенні величини кожного

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

По закінченню даної процедури величина елемента
,

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

вершини i у вершину j.

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

факту. Довжина найкоротшого шляху з вершини i у вершину j,

57