Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Double dist(int, int) const;
|
|
>;
Оба класса реализуют интерфейс АТД абстрактных кратчайших путей для нахождения кратчайших расстояний и путей. Этот интерфейс, который показан в программе 21.2, является обобщением интерфейса абстрактного транзитивного замыкания взвешенного орграфа для выяснения связности в орграфах, который изучался в главе 19. В обеих реализациях класса конструктор решает задачу поиска кратчайших путей для всех пар и сохраняет результат в приватных элементах данных. Кроме того, поддерживаются функции реализации запросов, которые возвращают длину кратчайшего пути из одной заданной вершины в другую, а также первое или последнее ребра в пути. Основное назначение такого АТД состоит в его практическом использовании для реализации алгоритмов поиска кратчайших путей для всех пар.
Глава 21. Кратчайшие пути
Программа 21.3. Вычисление диаметра сети
Эта клиентская функция иллюстрирует использование интерфейса из программы 21.2. Она находит наиболее длинный из кратчайших путей в данной сети, распечатывает путь и возвращает его вес (т.е. диаметр сети).
template < class Graph, class Edge> double diameter(Graph & G) { int vmax = 0, wmax = 0; allSP< Graph, Edge> all(G); for (int v = 0; v < G.V(); v++) for (int w = 0; w < G.V(); w++) if (all.path(v, w))
if (all.dist(v, w) > all.dist(vmax, wmax))
{ vmax = v; wmax = w; } int v = vmax; cout «v; while (v! = wmax)
{ v = all.path(v, wmax)-> w(); cout «" -" «v; } return all.dist(vmax, wmax);
|
| Программа 21.3 представляет собой типовую клиентскую программу, которая при поиске взвешенного диаметра (weighted diameter) сети использует интерфейс АТД для поиска всех кратчайших путей. Она проверяет все пары вершин, чтобы найти такую пару, для которой длина кратчайшего пути максимальна; затем она обходит путь, ребро за ребром. На рис. 21.13 показан путь, вычисленный этой программой для нашего примера эвклидовой сети. Цель алгоритмов этого раздела состоит в обеспечении линейного времени выполнения функций запроса. Как правило, мы ожидаем, что будет огромное количество таких запросов, поэтому мы готовы к существенным затратам ресурсов на представление приватных элементов данных и предварительную обработку в конструкторе, что будет содей- |
ствовать быстрым ответам на запросы. Оба рассматриваемых нами алгоритма требуют области памяти для приватных элементов данных, пропорциональной V2.
Основной недостаток этого общего подхода состоит в том, что для огромной сети мы не можем иметь достаточного объема доступной памяти (или не можем предоставить необходимое время на предварительную обработку). В принципе, наш интерфейс предоставляет свободу выбора между временными затратами на предварительную обработку и затратами памяти при обработке запроса. Если мы ожидаем только несколько запросов, предварительную обработку можно не делать, а просто выполнять для каждого запроса единственный алгоритм; тем не менее, существуют ситуации, требующие более совершенных алгоритмов (см. упражнения 21.48—21.50). Эта задача обобщает ту, которой мы посвятили большую часть главы 19 и связана с поддержкой быстрых запросов достижимости при ограниченном пространстве памяти.
РИСУНОК 21.13. ДИАМЕТР СЕТИ
Наибольший элемент в матрице всех кратчайших путей сети представляет собой диаметр сети. Диаметр сети — это длина наиболее длинного из кратчайших путей, показанных здесь для типовой эвклидовой сети.
Часть 5. Алгоритмы на графах
Первая рассматриваемая реализация функций АТД поиска кратчайших путей для всех пар решает эту задачу за счет использования алгоритма Дейкстры для решения в отношении каждой вершины задачи с единственным источником. В C++ можно написать этот метод непосредственно, как показано в программе 21.4: для решения задачи с единственным источником для каэдой вершины строится один вектор объектов SPT. Этот прием обобщает основанный на BFS метод для невзвешенных неориентированных графов, который рассматривался в разделе 17.7. Это также похоже на использование DFS в программе 19.4, где вычисляется транзитивное замыкание невзвешенного орграфа с началом в каждой вершине.
Программа 21.4. Алгоритм Дейкстры для поиска всех кратчайших путей___________
Этот класс использует алгоритм Дейкстры построения SPT для каждой вершины так, чтобы можно было вычислить pathR и запросить dist для любой пары вершин.
#include " SPT.cc"
template < class Graph, class Edge> class allSP
{ const Graph & G;
vector< SPT< Graph, Edge> ♦ > A; public:
allSP(const Graph & G): G(G), A(G.V()) { for (int s = 0; s < G.V(); s++)
A[s] = new SPT< Graph, Edge> (G, s); } Edge *pathR(int s, int t) const
{ return A[s]-> pathR(t); } double dist (int s, int t) const { return A[s]-> dist(t); >
>;
Свойство 21 7. С помощью алгоритма Дейкстры можно найти все кратчайшие пути в сети с неотрицательными весами за время, пропорциональное VE logdV, где d — 2, если Е < 2V, и d = E/V в противном случае.
Доказательство'. Непосредственно следует из свойства 21.6. ■
Как и в задачах о кратчайших путях для единственного источника с MST, эта граница завышена; время счета VE оказывается таким же, как и для типовых графов.
Чтобы сравнить эту реализацию с другими, полезно изучить матрицы, скрытые в структуре вектора векторов приватных элементов данных. Векторы wt формируют точно такую же матрицу расстояний, как та, которую мы рассматривали в разделе 21 1: элемент на пересечении строки s и столбца t есть длина кратчайшего пути из s в tКак показано на рис. 21.8 и 21.9, векторы spt перенесены из матрицы путей: элемент на пересечении строки s и столбца t представляет собой последний элемент в кратчайшем пути из s в t.
Для насыщенных графов можно было бы использовать представление в виде матрицы смежности и избежать вычисления обратного графа за счет неявного транспонирования матрицы (обмен индексами строк и столбцов), как в программе 19.7. Разработка реализации по этому плану представляет собой интересное упражнение по программированию и приводит к компактной реализации (см. упражнение 21.43); тем не менее, другой подход, который рассматривается немного ниже, допускает даже более компактную реализацию.