Начальные значения для рекуррентного соотношения (26.12) таковы:

;(о) = f X(i,j) если г ф j, %з у l0A(i,j) если г = j.

В самом деле, путь из одного ребра имеет метку, равную метку этого ребра, а пустой путь имеет метку 1 в соответствии с нашим соглашением; этот путь надо учесть при г = j.

Мы приходим к алгоритму, использующему метод динамического программирования для последовательного отыскания величин iff при к = 0,1, 2 ... , га; его ответом является матрица = (iff) (соответствующая «суммированию» по всем путям без ограничений на промежуточные вершины).

{\sc Compute-Summaries}!(\lambda,V)$\\ $n\leftarrowV$\\ I for $i\leftarrowl$ to $n$\\

I do for $j\leftarrowl$ to $n$\\ I do if $i=j$\\

I then $l~{(0)} {ij}\leftarrow\barl\oplus\lambda(i I else $l~{(0)} {ij}\leftarrow\lambda(i,j)$\\ r $k\leftarrowl$ to $n$\\ I do for $i\leftarrowl$ to $n$\\

I do for $j\leftarrowl$ to $n$\\

I do $l4(k)> {ij>=l4(k-l)> {ij>\oplus(l4(k-l)> -odot(l~{(k-l)> {kk»~{\ast>\odot l~{(k-l)} {kj})$\\ \verbll return $L~{(n)}$

Время работы данного алгоритма зависит от времени выполнения операций 0, © и *. Обозначив время выполнения операций через Tq, Гф, Г*, общее время работы алгоритма Compute-Summaries можно записать как ©(га3)(Tq + Гф +Г*)), что превращается в 0(га3), если время выполнения любой из трёх операций составляет 0(1).

Упражнения

26.4-1 Проверьте, что S\ = (К° U {оо}, min,+, оо, 0) и S3 = ({0,1}, V, Л, 0,1}) являются замкнутыми полукольцами.

26.4-2 Проверьте, что = (R U { - сю, +00}, min, +, +00, 0) является закнутым полукольцом. Чему равно значение а + ( - оо) для a G М? Что можно сказать о значении ( - оо) + (+оо)?

26.4-3 Запишите алгоритм Compute-Summaries для случая замкнутого полукольца 5*2, аналогичный алгоритму Флойда-Уоршолла. Чему должно быть равно значение -оо + оо, чтобы алгоритм правильно искад длины кратчайших путей?

26.4-4 Является ли S4 = (М,+, •, 0,1) замкнутым полукольцом? (Точнее следовало бы спросить так: можно ли его превратить в замкнутое полукольцо, определив каким-либо образом сумму любого бесконечного ряда?)

26.4-5 Можем ли мы обобщить на случай проивзольного замкнутого полукольца алгоритм Дейкстры? Алгоритм Беллмана-Форда? Процедуру Faster-All-Pairs-Shortest-Paths?

26.4-6

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

Задачи

26-1 Транзитивное замыкание растущего графа Мы хотим вычислять транзитивное замыкание ориентированного графа G = (V,E), множество рёбер которого растёт. Другими словами, мы хотим обновлять транзитивное замыкание после добавления в граф ещё одного ребра. Мы считаем, что изначально граф G не имел рёбер вовсе. Транзитивное замыкание должно храниться в булевой матрице.

a.Покажите, как за время 0(V2) можно произвести обновление транзитивного замыкания после добавления в граф G нового ребра.

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

c.Постройте алгоритм обновления транзитивного замыкания графа после добавления рёбер, для которого суммарное время работы при добавлении любой последовательности рёбер не превосходит 0(V3).

26-2 Кратчайшие пути в е-плотных графах

Граф G = (V, Е) называется s-плотным, если \Е\ = 0(С1+е) для некоторой константы е, лежащей в диапазоне 0 < е 1. Использование d-ичных куч (см. задачу 7-2) в алгоритме поиска кратчайших путей на е-плотных графах позволяет избавиться от использования фибоначчиевых куч (довольно сложной структуры данных), сохранив ту же асимптотическую оценку времени работы.

a.Определите асимптотику времени работы процедур Insert, Extract-Min и Decrease-Key как функцию от d и п (здесь п - число элементов d-ичной кучи). Что получается при d = Q(na), где 0 < а 1 - некоторая константа. Сравните эти времена с учётными временами этих операций для фибонначиевых куч.

b.Придумайте способ вычислить кратчайшие пути из одной вершины в е-плотном ориентированном графе G = (V, Е) без рёбер отрицательного веса за время О(Е). (Указание: выберите подходящее d как функцию е.)

c.Покажите, что можно вычислить кратчайшие пути для всех пар вершин в е-плотном ориентированном графе G = (V, Е) без рёбер отрицительного веса за время 0(VE).

d. Покажите, что за время 0(VE) можно вычислить кратчайшие пути для всех пар вершин в е-плотном ориентированном графе G = (V,E), который может иметь рёбра отрицательного веса, но не содержит циклов отрицательного веса.

26-3 Минимальный остов и замкнутое полукольцо Пусть G = (V, Е) - связный неориентированный граф с весовой функций w : Е -> Ж, вершинами которого являются числа от 1 до п. Предположим, что веса w(i,j) всех рёбер различны. Пусть Т - единственный (см. упр. 24.1-6) минимальный остов графа G. Маге (B.M.Maggs) и С.А.Плоткин предложили использовать замкнутое полукольцо для отыскания минимального покрывающего дерева. Для каждой пары вершин определим минимаксный вес (minimax weight) rriij взяв минимум по всем путям максимумов весов рёбер на каждом пути.

a.Покажите, что s = (м. U { - оо, оо}, min, max, оо, -оо) является замкнутым полукольцом.

Таким образом, мы можем использовать процедуру Compute-Summapjes для вычисления минимаксных весов rriij в графе G.

(к)

Обозначим через т- минимаксный вес для всех путей из i в j с промежуточными вершинами из множества {1, 2, • • • , к}.

(к)

b.Напишите рекуррентную формулу для т- при к 0.

c.Пусть Тт =G Е : w(i,j) = rriij}. Докажите, что ребра из Тт образуют покрывающее дерево для графа G.

d.Покажите, что это покрывающее дерево будет минимальным. (Указание. Посмотрите, что происходит при добавлении ребра в Г и одновременном удалении из Т какого-нибудь ребра, лежащего на пути из г в j. Посмотрите также, что происходит при замене ребра из Т на другое ребро.)

Замечания

Лоулер [132] подробно рассматривает задачу нахождения кратчайших путей для всех пар вершин, хотя и не выделяет отдельно случай разреженных графов (при этом связь задачи о кратчайших путях с умножением матриц относится к фольклору). Алгоритм Флойда-Уоршолла описан в работе Флойда [68], который опирается результат Уоршолла [198] (о транзитивным замыкании булевых матриц). Понятие замкнутого полукольца появилось в книге Ахо, Хопкофта и Ульмана [4]. Алгоритм Джонсона взят из [114].