Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21. Кратчайшие пути. 21.46. Дайте пример матрицы, в которой элемент в строке s и столбце tравен коли честву различных простых направленных путей
|
|
21.46. 
Дайте пример матрицы, в которой элемент в строке s и столбце tравен коли
честву различных простых направленных путей, соединяющих s и t на рис. 21.1.
21.47. Реализуйте класс, конструктор которого вычисляет матрицу числа путей, опи
санную в упражнении 21.46 так, чтобы за линейное время можно было получить зап
рос числа через общедоступную функцию-элемент.
21.48. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей
для разреженных графов, в которой расход памяти сокращается до величин, пропор
циональных V, а время запроса увеличивается до значений, пропорциональных V.
• 21.49. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей
для разреженных графов, в которой расход памяти существенно меньше O(V2), но ко
торая поддерживает запросы за время, намного меньшее O(V). Указание: Вычислите
все кратчайшие пути для подмножества вершин.
• 21.50. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей
для разреженных графов, в которой расход памяти существенно меньше O(V2), и (с
использованием рандомизации) поддерживаются запросы за линейное ожидаемое вре
мя.
о 21.51. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей, в которой используется отложенный подход применения алгоритма Дейкстры для построения SPT (и связанного с ним вектора расстояний) из каждой вершины s: алгоритм выполняется в первом запросе клиентом кратчайшего пути из s, а затем при ссылке на кратчайший путь в последующих запросах.
о 21.52. Измените АТД кратчайших путей и алгоритм Дейкстры, чтобы произвести вычисления кратчайших путей в сетях, в которых веса ставятся в соответствие как вершинам, так и ребрам. Не создавайте снова представление графа (этот метод описан в упражнении 21.4), а просто измените код.
21.53. Постройте небольшую модель маршрутов авиалиний и времен перелета, возможно, основанную на некоторых перелетах, совершенных вами. Воспользуйтесь своим решением упражнения 21.52 для вычисления наиболее быстрого пути для перемещения от одного из обслуживаемых адресатов к другому. Затем протестируйте полученную программу на реальных данных (см. упражнение 21.5).
|
|