Глава 21. Кратчайшие пути. 21.46. Дайте пример матрицы, в которой элемент в строке s и столбце tравен коли­ честву различных простых направленных путей

21.46. Дайте пример матрицы, в которой элемент в строке s и столбце tравен коли­
честву различных простых направленных путей, соединяющих s и t на рис. 21.1.

21.47. Реализуйте класс, конструктор которого вычисляет матрицу числа путей, опи­
санную в упражнении 21.46 так, чтобы за линейное время можно было получить зап­
рос числа через общедоступную функцию-элемент.

21.48. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей
для разреженных графов, в которой расход памяти сокращается до величин, пропор­
циональных V, а время запроса увеличивается до значений, пропорциональных V.

• 21.49. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей
для разреженных графов, в которой расход памяти существенно меньше O(V²), но ко­
торая поддерживает запросы за время, намного меньшее O(V). Указание: Вычислите
все кратчайшие пути для подмножества вершин.

• 21.50. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей
для разреженных графов, в которой расход памяти существенно меньше O(V²), и (с
использованием рандомизации) поддерживаются запросы за линейное ожидаемое вре­
мя.

о 21.51. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей, в которой используется отложенный подход применения алгоритма Дейкстры для по­строения SPT (и связанного с ним вектора расстояний) из каждой вершины s: алго­ритм выполняется в первом запросе клиентом кратчайшего пути из s, а затем при ссылке на кратчайший путь в последующих запросах.

о 21.52. Измените АТД кратчайших путей и алгоритм Дейкстры, чтобы произвести вы­числения кратчайших путей в сетях, в которых веса ставятся в соответствие как вер­шинам, так и ребрам. Не создавайте снова представление графа (этот метод описан в упражнении 21.4), а просто измените код.

21.53. Постройте небольшую модель маршрутов авиалиний и времен перелета, воз­можно, основанную на некоторых перелетах, совершенных вами. Воспользуйтесь сво­им решением упражнения 21.52 для вычисления наиболее быстрого пути для переме­щения от одного из обслуживаемых адресатов к другому. Затем протестируйте полученную программу на реальных данных (см. упражнение 21.5).