Часть 5. Алгоритмы на графах. > 21.127.Разработайте класс, основанный на алгоритме Беллмана-Форда, который обес­ печивает клиентов возможностью проверить существование в сети

> 21.127. Разработайте класс, основанный на алгоритме Беллмана-Форда, который обес­
печивает клиентов возможностью проверить существование в сети отрицательных цик­
лов, используя фиктивную вершину с ребрами во все вершины сети.

о 21.128. Приведите семейство графов, для которых программа 21.9 на поиск отрица­тельных циклов затрачивает время, пропорциональное VE.

> 21.129. Покажите расписание, которое вычисляется программой 21.9 для задачи ка­
лендарного планирования с конечными сроками, описанной в упражнении 21.89.

о 21.130. Докажите, что следующий общий алгоритм решает задачу поиска кратчайших путей с единственным источником: " ослабить произвольное ребро; продолжать так до тех пор, пока существуют ребра, которые можно ослабить".

21.131. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, восполь­зовавшись рандомизированной очередью вместо очереди FIFO. (Результаты решения упражнения 21.130 доказывают, что этот метод допустимый.)

о 21.132. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, чтобы вместо очереди FIFO использовать такую очередь с двусторонним доступом, в кото­рую ребра помещаются в соответствии со следующим правилом: если ребро уже на­ходится в очереди с двусторонним доступом, поместить его в ее начало (как в стеке), а если оно встречается в первый раз, то поместить его в ее конец (как в обычной оче­реди).

21.133. Проведите эмпирические исследования с целью сравнения производительно­сти реализаций из упражнений 21.131 и 21.132 с программой 21.9 на различных общих сетях (см. упражнения 21.109—21.111).

о 21.134. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, чтобы ре­ализовать функцию, которая возвращает индекс произвольной вершины в произволь­ном отрицательном цикле или -1, если сеть не содержит отрицательных циклов. Ког­да отрицательный цикл присутствует, эта функция должна также построить вектор spt, такой что за счет обычного следования по связям в этом векторе (начиная с возвра­щаемого значения), можно пройти вдоль цикла.

о 21.135. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, чтобы ус­тановить веса вершин так, как это требуется для алгоритма Джонсона, воспользовав­шись следующим методом. Каждый раз, когда очередь становится пустой, сканируется вектор spt, чтобы найти вершину, вес которой еще не установлен, и алгоритм запус­кается повторно с этой вершиной в качестве источника (для установки весов всех вер­шин, находящихся в той же сильно связной компоненте, что и новый источник); опи­санная процедура продолжается, пока не будут обработаны все сильно связные компоненты.

> 21.136. Разработайте реализацию интерфейса АТД поиска кратчайших путей для всех
пар в разреженных сетях (основанную на алгоритме Джонсона) за счет внесения со­
ответствующих изменений в программы 21.9 и 21.4.

21.137. Разработайте реализацию интерфейса АТД поиска кратчайших путей для всех пар в плотных сетях (основанную на алгоритме Джонсона) (см. упражнения 21.136 и 21.43). Проведите эмпирические исследования с целью сравнения полученной реали­зации с алгоритмом Флойда (программа 21.5) на различных общих сетях (см. упраж­нения 21.109-21.111).