5.6. ЗАДАЧИ НАХОЖДЕНИЯ ПУТЕЙ

В этом разделе мы изучим две часто встречающиеся задачи, касающиеся путей, соединяющих узлы. В дальнейшем будет ориентированным графом. (Рефлексивным и) транзитивным замыканием графа называется граф который содержит то же множество узлов, что и но в котором из и в до идет ребро тогда и только тогда, когда в существует путь (длины или больше) из и в до.

С задачей нахождения транзитивного замыкания графа тесно связана задача о кратчайшем пути. Поставим в соответствие каждому ребру графа неотрицательную стоимость с Стоимость пути определяется как сумма стоимостей ребер, образующих его. Задача о кратчайшем пути состоит в нахождении для каждой пары узлов ( пути наименьшей стоимости среди всех путей из

Оказывается, что идеи, на которых основаны лучшие из известных алгоритмов нахождения транзитивного замыкания и кратчайшего пути, являются (простыми) частными случаями соображений, исходя из которых решается задача нахождения (бесконечного) множества всех путей между каждой парой узлов. Чтобы обсудить эту задачу во всей ее общности, введем специальную алгебраическую структуру.

Определение. Замкнутым полукольцом называется система

где множество элементов, а бинарные операции на обладающие следующими пятью свойствами:

1) - моноид, т. е. множество замкнуто относительно для всех из операция ассоциативна для всех с из и служит единичным элементом для всех а из Тройка также является моноидом. Кроме того, мы предполагаем, что служит аннулятором, т. е.

2) Операция коммутативна и идемпотентна

3) Операция дистрибутивна относительно

4) Если счетная последовательность элементов из то сумма существует и единственна. Более того, ассоциативность, коммутативность и идемпотентность выполняются не только для конечных, но и для бесконечных сумм.

5) Операция дистрибутивна не только относительно конечных сумм, но и относительно счетных (это не следует из свойства 3). Таким образом, из свойств 4 и 5 вытекает, что

Пример 5.9. Приведем три системы замкнутых полуколец.

1. Пусть ), а сложение и умножение заданы таблицами

Свойства 1—3 проверить легко. Что касается свойств 4 и 5, то заметим, что счетная сумма равна тогда и только тогда, когда все слагаемые равны 0.

2. Пусть где множество неотрицательных вещественных чисел, включая Легко проверить, что служит единичным элементом для для

3. Пусть 2 — конечный алфавит (т. е. множество символов) и где семейство множеств, состоящих из конечных цепочек символов из 2, включая пустую цепочку в (т. е. цепочку длины 0). Здесь обозначает операцию объединения

множеств, а их конкатенацию 1). Единичным элементом для и служит 0, а для Свойства 1—3 читатель может проверить сам. Что касается свойств 4 и 5, то достаточно заметить, что счетные объединения определяются такой эквивалентностью: равносильно для некоторого

Центральной операцией в нашем анализе замкнутых полуколец будет унарная операция называемая замыканием. Если — замкнутое полукольцо и то положим где Иными словами, значение а равно бесконечной сумме Заметим, что свойство 4 определения замкнутого полукольца гарантирует, что а Из свойств 4 и 5 вытекает равенство Отметим, что

Пример 5.10. Рассмотрим полукольца из примера 5.9. В выполняется для или 1. В равенство выполнено для всех а выполняется для для всех Например,

т. е. состоит из всех цепочек символов включая пустую цепочку. Вообще , где обозначает множество-степень для

Теперь возьмем ориентированный граф в котором каждое ребро помечено элементом некоторого замкнутого полукольца Определим метку пути как произведение меток ребер, составляющих этот путь, причем метки берутся в порядке прохождения ребер. В частности, метка пути нулевой длины равна 1 (единичному элементу для операции рассматриваемого полукольца). Для каждой пары узлов определим с ( как сумму меток всех путей между Назовем с ( стоимостью прохождения из у в Условимся считать, что сумма по пустому множеству путей равна (единичному элементу для операции нашего полукольца). Заметим, что если имеет циклы, то между может быть бесконечно много путей, но аксиомы замкнутого полукольца гарантируют, что определяется корректно.

Пример 5.11. Рассмотрим ориентированный граф на рис. 5.17, в котором каждое ребро помечено элементом полукольца описанного в примере 5.9. Метка пути равна Простой

1) Конкатенацией множеств называется множество

2) Читателю следует не упустить из виду аналогию между рассматриваемой ситуацией и недетерминированным конечным автоматом (см. Хопкрофт, Ульман [1969] или Ахо, Ульман [1972]), который мы еще обсудим в разд. 9.1. Там узлы представляют собой состояния, а метки ребер — символы из некоторого конечного алфавита.

Рис. 5.17. Помеченный ориентированный граф.

цикл из имеет метку Вообще каждый путь положительной длины, идущий из имеет метку 0. Однако стоимость пути нулевой длины из равна 1. Следовательно,

Изложим алгоритм вычисления для всех пар узлов Основными шагами этого алгоритма, занимающими единицу времени, будут операции и произвольного замкнутого полукольца. Конечно, для таких структур, как множество всех множеств цепочек над некоторым алфавитом, не понятно, можно ли в принципе реализовать эти операции в отведенное им "единичное время". Но для тех полуколец, которыми мы будем пользоваться, эти операции легко выполнимы.

Алгоритм 5.5. Вычисление стоимости прохождения между узлами

Вход. Ориентированный граф где и функция разметки 1: где — замкнутое полукольцо. Полагаем если

Выход. Для всех заключенных между элемент с из равный сумме по всем путям из меток этих путей.

Метод. Вычисляем для всех и Величины задуманы как суммы меток путей, идущих из к,- в все узлы которых, кроме, быть может, концов, принадлежат множеству Например, путь рассматривается при вычислении но не Алгоритм выглядит так:

Теорема 5.5. Алгоритм 5.5 использует операций и из полукольца и вычисляет с для

Доказательство. Легко проверить, что строка 5 выполняется раз, причем каждый раз используются четыре операции, и -циклы в строках 1, 2 и 6 итерируются не более раз каждый. Поэтому достаточно операций.

Чтобы доказать корректность, надо доказать индукцией по что сумма меток всех путей из не содержащих промежуточных (т. е. отличных от концов) узлов с индексами, большими Базис, т. е. случай тривиален в силу строк 1 и 2, поскольку любой такой путь имеет длину или состоит из единственного ребра. Шаг индукции получается на основании строки 5, ибо путь из не содержащий промежуточных узлов с индексами, большими либо

1) не содержит промежуточных узлов с индексами, большими (слагаемое ), либо

2) идет из затем несколько раз (возможно, ни разу) из наконец, из в , причем везде на этих участках нет промежуточных узлов с индексами, большими (слагаемое

Аксиомы замкнутого кольца гарантируют, что в строке 5 корректно вычисляется сумма меток всех этих путей.