Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21, Кратчайшие пути. • 21.27.Реализуйте класс, который использует объекты SPT для выполнения анализа чув ствительности ребер сети по отношению к заданной паре вершин s и t
|
|
• 21.27. Реализуйте класс, который использует объекты SPT для выполнения анализа чув
ствительности ребер сети по отношению к заданной паре вершин s и t Вычислите та
кую матрицу размером V на V чтобы для каждого и и v элемент на пересечении стро
ки и и столбца v был равен 1, если в сети существует ребро u-v, вес которого может
быть увеличен без увеличения длины кратчайшего пути из s в / и равен 0 в противном
случае.
о 21.28. Реализуйте класс, который использует объекты SPT, чтобы отыскать кратчайший путь, соединяющий один заданный набор вершин с другим заданным набором вершин в заданной сети.
21.29. Воспользуйтесь своим решением из упражнения 21.28 для реализации клиент
ской функции, которая находит кратчайший путь от левого ребра к правому ребру в
случайной сети (см. упражнение 20.17).
21.30. Покажите, что MST неориентированного графа эквивалентно критическому ре
сурсу SPT этого графа: для каждой пары вершин v и w оно дает путь, соединяющий их,
в котором наиболее длинное ребро обладает минимально возможной длиной.
21.31. Выполните эмпирические исследования эффективности двух версий алгоритма
Дейкстры для разреженных графов, которые описаны в этом разделе (программа 21.1
и программа 20.7, с соответствующим определением приоритета), для различных се
тей (см. упражнения 21.4-21.8). Воспользуйтесь реализацией очереди с приоритетами
с помощью стандартного полного бинарного дерева.
21.32. Выполните эмпирические исследования с целью получения наилучшего значе
ния d, используя реализацию очереди с приоритетами в виде d-арного полного дере
ва (см. программу 20.10) для каждой из трех рассмотренных реализаций алгоритма PFS
(программы 18.10, 20.7 и 21.1), примененных на различных сетях (см. упражнения
21.4-21.8).
• 21.33. Выполните эмпирические исследования для определения эффекта от реализа
ции очереди с приоритетами в виде турнира индексно-сортирующего дерева (см. уп
ражнение 9.53) в программе 21.1 для различных сетей (см. упражнения 21.4 — 21.8).
о 21.34. Выполните эмпирические исследования с целью анализа высоты и средней длины пути в SPT для различных сетей (см. упражнения 21.4-21.8).
21.35. Разработайте класс для задачи поиска кратчайших путей типа источник-сток, который основывается на коде, подобном программе 21.1, но который инициализирует очередь с приоритетами и источником, и стоком. При таком подходе SPT растет из каждой вершины; ваша основная задача — принять решение, что делать, когда два SPT соприкасаются.
• 21.36. Опишите семейство графов с V вершинами и E ребрами, для которых дости
гается худший случай времени выполнения алгоритма Дейкстры.
•• 21.37. Разработайте приемлемый генератор случайных графов с V вершинами и Е ребрами, для которых время счета PFS-реализации алгоритма Дейкстры с использованием кучи является суперлинейным.
• 21.38. Напишите клиентскую программу графической анимацией динамики алгорит
ма Дейкстры. Ваша программа должна создавать изображения, подобные рис. 21.11 (см.
упражнения 17.56-17.60). Протестируйте программу на случайных эвклидовых сетях
(см. упражнение 21.9).
Часть 5. Алгоритмы на графах
21.3 Кратчайшие пути между всеми парами
В этом разделе мы рассмотрим два метода решения задачи поиска кратчайших путей для всех пар. Алгоритмы, которые планируется реализовать, непосредственно обобщают два базовых алгоритма, которые были рассмотрены в разделе 19.3 для задачи транзитивного замыкания. Первый метод заключается в выполнении алгоритма Дейкстры из каждой вершины для получения кратчайших путей из этой вершины во все остальные. Если мы реализуем очередь с приоритетами при помощи полного бинарного дерева, то при таком подходе время выполнения в худшем случае будет пропорционально VE lgV, однако за счет использования d-арного полного дерева мы можем улучшить эту границу, доведя ее для многих типов сетей до VE. Второй метод, который позволяет напрямую решить данную задачу за время, пропорциональное V3, является расширением алгоритма Уоршалла, известным как алгоритм Флойда (Floyd's algorithm).
Программа 21.2. АТД поиска кратчайших путей для всех пар_________________________
Все наши решения задачи о кратчайших путях для всех пар представляются в виде классов с конструктором и двумя функциями реализации запросов: dist, возвращающая длину кратчайшего пути из первого аргумента во второй, и одна из двух возможных функций вычисления пути: либо path, возвращающая указатель на первое ребро в кратчайшем пути, либо pathR, возвращающая указатель на конечное ребро в кратчайшем пути. Если такого пути не существует, то функция path возвращает 0, a dist не определена.
Мы используем функции path или pathR в зависимости от того, что удобнее для рассматриваемого алгоритма; на практике нам следовало бы поместить одну из них или другую (или обе) в интерфейс, а в реализациях использовать различные функции преобразования, как обсуждалось в разделе 21.1 и в упражнениях в конце этого раздела.
template < class Graph, class Edge> class SPall { public:
SPall(const Graph &);
Edge *path(int, int) const;
Edge *pathR(int, int) const;