Применение алгоритма Уоршалла

Алгоритм Уоршалла может быть модифицирован с целью получения матрицы, содержащей длины кратчайших путей между вершинами [Трамбле, Соренсон, 1982].

Опишем алгоритм [Липский, 1988]

Обозначим через d^(m)_ij длину кратчайшего из путей из v_i в v_j с промежуточными вершинами из множества {v₁,...,v_m}.

Тогда имеем следующие уравнения:

Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из v_i в v_j c промежуточными вершинами из множества {v₁,...,v_m,v_m+1}.

Если этот путь не содержит v_m+1, то разделив путь на отрезки от v_i до v_m+1 и от v_m+1 до v_j, получаем равенство:

d^(m+1)_ij=d^(m)_im+d^(m)_mj.

Соотношения позволяют вычислить расстояния d(v_i,v_j)=d⁽ⁿ⁾_ij.

Авторами приведенного алгоритма являются Уоршалл и Р.Флойд (Floyd R.W.).

Дата добавления: 2014-01-20; Просмотров: 342; Нарушение авторских прав?; Мы поможем в написании вашей работы!