![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. > 21.127.Разработайте класс, основанный на алгоритме Беллмана-Форда, который обес печивает клиентов возможностью проверить существование в сети
о 21.128. Приведите семейство графов, для которых программа 21.9 на поиск отрицательных циклов затрачивает время, пропорциональное VE. > 21.129. Покажите расписание, которое вычисляется программой 21.9 для задачи ка о 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.137. Разработайте реализацию интерфейса АТД поиска кратчайших путей для всех пар в плотных сетях (основанную на алгоритме Джонсона) (см. упражнения 21.136 и 21.43). Проведите эмпирические исследования с целью сравнения полученной реализации с алгоритмом Флойда (программа 21.5) на различных общих сетях (см. упражнения 21.109-21.111).
|