Обозначим lij длину дуги (xi, xj), если таковой не существует примем lij = ¥, кроме того, положим lii = 0. Обозначим длину кратчайшего из путей из xi в xj с промежуточными вершинами из множества { x 1, …, xm }. Тогда можно получить следующие уравнения
, (2)
. (3)
Уравнение (2) очевидно. Обоснуем уравнение (3). Рассмотрим кратчайший путь из xi в xj с промежуточными вершинами из множества { x 1, …, xm, xm +1}. Если этот путь не содержит xm +1, то . Если же он содержит xm +1, то деля путь на отрезки от xi до xm +1 и от xm +1 до xj, получаем равенство .
Уравнения (2) и (3) позволяют легко вычислить матрицу расстояний [ dij ] между всеми парами вершин графа G (X, E). На первом этапе согласно (2) составляем n ´ n матрицу равную матрице [ lij ] весов ребер (n – число вершин G (X, E)). n раз производим вычисление по итерационной формуле (3), после чего имеем – матрицу расстояний.
Отметим, что алгоритм Флойда непосредственно не указывает сам кратчайший путь между вершинами, а только его длину. Алгоритм Флойда можно модифицировать таким образом, чтобы можно было находить и сами пути. Для этого получим вспомогательную матрицу [ Rij ], которая будет содержать наибольший номер вершины некоторого кратчайшего пути из x i в x j (Rij =0, если этот путь не содержит промежуточных вершин).
|
|
Эта матрица вычисляется параллельно с по следующим правилам
Последнее выражение следует из обоснования (3).
Теперь кратчайший путь выписывается из следующего рекурсивного алгоритма:
Кратчайший путь из xi в xj:
1°. Если Rij = 0 то выполнить 2°,
иначе выполнить 3°.
2°. Если i = j то выписать xi и закончить,
иначе выписать xi и xj закончить.
3°. Выписать кратчайший путь между xi и .
4°. Выписать кратчайший путь между и xj.
Пункты 3° и 4° предполагают рекурсивное обращение к рассмотренному алгоритму.
С задачей определения кратчайших путей в графе тесно связана задача транзитивного замыкания бинарного отношения.
Напомним, что бинарным отношением на множестве Х называется произвольное подмножество E Ì X ´ X.
Транзитивным называется отношение, удовлетворяющее следующему условию: если (x, y) Î E и (y, z) Î E, то (x, z) Î E для всех x, y, z Î X. Отметим, что бинарное отношение можно однозначно представить орграфом G (X, E). Теперь для произвольного отношения Е определим новое отношение Е * следующим образом
E * = {(x, y) | если в G (X, E) существует путь ненулевой длины из x в y }.
Легко проверить, что Е * - транзитивное отношение. Кроме того, Е * является наименьшим транзитивным отношением на Х в том смысле, что для произвольного транзитивного отношения F É E выполняется E * É F. Отношение Е * называется транзитивным замыканием отношения Е.
Если отношение Е представить в виде графа G (X, E) в котором каждая дуга имеет вес 1, то транзитивное замыкание Е * можно вычислить с помощью алгоритма Флойда. При этом надо учесть, что
|
|
(xi, xj) Î E * если .
Для большего удобства алгоритм Флойда в этом случае можно модифицировать следующим образом.
Положим
.
Вместо (3) запишем
,
где Ú – дизъюнкция (логическое сложение),
Ù – конъюнкция (логическое умножение).
После завершения работы алгоритма будем иметь
Модифицированный таким образом алгоритм называется алгоритмом Уоршелла.
ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ
[1] Система переключательных функций называется независимой, если ни одна из входящих в нее функций не выражается через другие функции этой же системы с помощью операций суперпозиции или подстановки аргументов.