Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 125

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 119 120 121 122 123 124 < 125 > 126 127 128 129 130 131 .. 161 >> Следующая

Если теперь попытаться найти кратчайший путь между вершинами 3 и 4, то будет найден путь, проходящий через вершины 3, 0, 1, 4. Суммарная длина этого пути составляет 6 единиц и, хотя и существует путь, проходящий через меньшее число вершин (3, 0,4), но его суммарная длина оказывается больше (8 единиц), так что в качестве кратчайшего будет выбран именно первый путь.
Вызовем для этого графа метод getDijkstraPath с параметрами для нахождения кратчайшего пути из вершины 3 в вершину 4 (параметр arcweight задает нагрузку на граф) и напечатаем получившийся путь:
vector<int> path;
cout « "The shortest path from 3 to 4 is "
« graph.getDijkstraPath(3, 4, arcsWeight, path)
« " and traverses the following vertices:" « endl; for (vector<int>::iterator it = path.begin(); it != path.end(); ++it) { cout « *it « "; ";
}
cout « endl;
Тогда в результате получится следующий текст:
The shortest path from 3 to 4 is 6 and traverses the following vertices:
3; 0; 1; 4;
На каждом шаге алгоритм Дейкстры выбирает пограничную вершину, просматривая множество, состоящее из последовательно уменьшающегося множества вершин, а после выбора пограничной вершины просматривает все исходящие из нее дуги. Если граф имеет п вершин и m дуг, то на каждом из п
360
Гпава 6
шагов алгоритма (в худшем случае) рассматривается вплоть до п вершин, а поскольку каждая дуга, в конце концов, будет просмотрена по одному разу, то всего будут просмотрены все т дуг. Это означает, что в худшем случае скорость работы алгоритма приближается к n х п + т. Для больших графов это оказывается довольно существенной величиной.
Некоторого ускорения можно добиться, если организовать поиск пограничной вершины более эффективно. Например, массив минимальных расстояний dist можно упорядочить по возрастанию (правда, тогда в массиве придется хранить не только сами расстояния, но и номера соответствующих вершин). В этом случае поиск пограничной вершины вообще будет производиться за постоянное время, не зависящее от числа вершин и структуры графа, однако при изменении содержимого массива потребуется перемещать в нем измененный элемент, чтобы не нарушить упорядоченности элементов. Это может потребовать времени, пропорционального log2«. Еще удобнее будет организация массива расстояний в виде пирамиды так же, как мы делали это в реализации алгоритма пирамидальной сортировки в разд. 2.2. В обоих случаях наихудшее время работы алгоритма сокращается до n х log2« + т элементарных шагов. В следующем разделе организация массива расстояний в виде пирамиды используется в алгоритме определения минимального остовного дерева графа.
Рассмотрим теперь задачу, в которой требуется найти всевозможные кратчайшие пути из всех вершин графа во все другие вершины. Результатом работы такого алгоритма должна быть матрица, в которой для каждой пары вершин (/,/) содержится длина минимального пути из вершины i в вершину j. Для нахождения самих путей можно также построить матрицу, в которой в клетке (/,/) содержится номер первой вершины на кратчайшем пути из вершины / в вершину j. Разумеется, можно воспользоваться алгоритмом Дейкстры, применив его последовательно для всех пар вершин, однако эффективность работы подобного способа будет невелика.
Прежде чем перейти к рассмотрению алгоритма для решения приведенной задачи, рассмотрим еще одну задачу, вообще говоря, более простую. Ее обобщение даст нам искомый алгоритм. Задача состоит в том, чтобы для заданного графа G найти его транзитивное замыкание, т. е. граф G1 такой, что в нем дуга ведет из вершины / в вершину j только в том случае, если в исходном графе существовал путь из вершины i в вершину^'. Разумеется, исходный граф G будет содержаться в результирующем графе G7 в качестве подграфа.
Для решения этой задачи удобно воспользоваться представлением графа в виде матрицы смежности (M-граф), т. к. операции над матрицами удачно представляют собой отдельные шаги алгоритма.
Напомним, что матрица смежности — это матрица размером n х п элементов (где п — число вершин графа), каждый элемент которой с индексами (/,/)
Алгоритмы обработки графов
361
содержит логическое значение true, если в графе имеется дуга, ведущая из вершины / в вершину у, и значение false — в противном случае. Если ввести операции сложения и умножения для логических значений, взяв в качестве операции сложения операцию ИЛИ над логическими значениями, а в качестве операции умножения — операцию И, то можно, используя обычные правила для умножения матриц, определить и операцию умножения матриц смежности друг на друга, в результате которой получается новая матрица смежности.
Если матрица А представляет собой матрицу смежности графа Ga, а матрица В — матрицу смежности графа GB с теми же вершинами, то матрица А х В будет представлять собой матрицу графа, в котором дуга ведет из вершины i в вершину j в том и только в том случае, когда существует вершина к, такая, что в графе А имеется дуга, ведущая из вершины / в вершину к, а в графе В — дуга, ведущая из вершины к в вершину j. Это позволяет построить алгоритм нахождения транзитивного замыкания графа, используя только операции умножения над матрицами смежности различных промежуточных графов.
Предыдущая << 1 .. 119 120 121 122 123 124 < 125 > 126 127 128 129 130 131 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.