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

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

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

задать 0 и 8, то в результате работы будет получен пустой вектор.
Более интересная задача состоит в том, чтобы найти кратчайший путь между двумя вершинами при условии, что каждая дуга имеет определенную длину, так что мерой такого расстояния будет не количество дуг на кратчайшем пути, а суммарная длина пути.
Опишем алгоритм нахождения такого пути при условии, что длины всех дуг неотрицательны. Этот алгоритм был предложен и опубликован Э. Дейкстрой (Е. W. Dijkstra), поэтому и носит его имя.
Алгоритм поиска кратчайшего пути в этом случае также несколько напоминает алгоритм обхода графа в ширину и состоит в следующем. Будем рассматривать два множества: множество вершин, для которых уже известен кратчайший путь до них из начальной вершины (passed), и множество еще не исследованных вершин (notPassed).
В начале работы первое множество будет пустым, а второе будет содержать все вершины графа. На каждом шаге работы алгоритма из второго множества в первое переводится одна вершина — та, расстояние до которой от исходной вершины минимально. Эту вершину будем называть пограничной (border).
Для определения пограничной вершины во время работы алгоритма постоянно корректируется массив расстояний dist, в котором для каждой вершины хранится расстояние до нее от исходной вершины, если оно известно. В начале работы алгоритма расстояние известно только для одной вершины — начальной. Конечно, это расстояние равно нулю, так что эта вершина и будет выбрана первой в качестве пограничной. В дальнейшем массив будет корректироваться за счет просмотра вершин-кандидатов, в которые ведут дуги из очередной пограничной вершины в еще не просмотренные вершины.
Как и в предыдущем алгоритме, сам путь из начальной вершины в конечную будет сохраняться с помощью массива меток backs. Алгоритм заканчивает работу, как только в качестве пограничной будет выбрана конечная вершина
Алгоритмы обработки графов
357
или, если окажется, что очередная пограничная вершина вообще не связана с начальной (находится на бесконечно большом расстоянии от нее). Это расстояние задается в программе константой infinity.
Реализация этого алгоритма приведена в листинге 6.9 в виде метода getDijkstraPath класса ListGraph. В качестве аргументов методу передаются номера начальной и конечной вершин на кратчайшем пути, а также переменная, которая будет содержать вектор номеров промежуточных вершин на пути из начальной вершины в конечную. Результатом работы метода будет суммарная длина кратчайшего пути.
Чтобы задать нагрузку на дуги, не изменяя представления графа, введем специальный абстрактный тип данных Graphweight, представляющий объекты, задающие нагрузку на дуги графа. Главным методом соответствующего класса будет функция arcLength, которая по заданным номерам вершин определяет длину дуги, соединяющей эти вершины. Значение функции будем считать неопределенным, если заданные вершины не соединены никакой дугой или вообще не задают номеров вершин графа. Чтобы задать конкретную нагрузку на граф, необходимо определить реализацию абстрактного типа данных
GraphWeight.
| Листинг 6.9. Алгоритм определения кратчайшего пути с учетом длин дуг
double ListGraph::getDijkstraPath(int beg, int end,
const Graphweight & weights, vector<int> & path) const {
path.clear();
// Множество непросмотренных вершин:
Set notPassed(0, vertexCount()-1); notPassed.addScale(0, vertexCount()-1);
// Массив обратных меток
int *backs = new int[vertexCount()];
// Массив минимальных расстояний. В начале работы все расстояния // бесконечно большие, кроме расстояния до исходной вершины double *dist = new double[vertexCount()];
for (int i = 0; i < vertexCount(); i++) dist[i] = INFINITY; dist[beg] = 0;
// Цикл поиска и обработки пограничной вершины while(!notPassed.empty()) {
// Поиск пограничной вершины: просматриваем массив dist // в поисках вершины с минимальным расстоянием от beg int border = -1;
358
Гпава 6
double minDist = INFINITY;
Iterator<int> *check = notPassed.iterator(); while(check->hasMoreElements()) { int next = **check; if (dist[next] < minDist) { minDist = dist[border = next];
}
++*check;
}
delete check;
// Если пограничная вершина не найдена, то пути нет if (border == -1) return INFINITY;
// Если пограничная вершина совпала с конечной,
// то переходим к формированию результата if (border == end) break;
// Обработка вершин, смежных с пограничной notPassed -= border;
Iterator<int> *nextToBorder = graph[border].iterator(); while (nextToBorder->hasMoreElements()) { int v = **nextToBorder; if (notPassed.has(v) && dist[v] >
dist[border] + weights.arcLength(border, v)) { backs[v] = border;
dist[v] = dist[border] + weights.arcLength(border, v);
}
++*nextToBorder;
}
delete nextToBorder;
// Формирование результирующего вектора int current = end; while(current != beg) {
path.insert(path.begin(), current); current = backs[current];
}
path.insert(path.begin(), beg);
return dist[end];
}
Алгоритмы обработки графов
359
Для примера нагрузим дуги графа рис. 6.1 некоторыми целыми числами, обозначающими длину дуги. В результате получится граф, изображенный на рис. 6.4.
Предыдущая << 1 .. 118 119 120 121 122 123 < 124 > 125 126 127 128 129 130 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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