Графы-2: минимизация на матрице весов

Цель

Рассмотреть работу с графом, представленном матрицей весов рёбер, на примере алгоритмов построения минимального остова и нахождения кратчайших путей.

Код

Алгоритмы выполнены в виде функций-шаблонов, принимающих аргументы пяти основных типов:

  1. Индексы/количества вершин. Используется тип unsigned.
  2. Матрица весов/расстояний (параметр шаблона WeightMatrix), доступ к элементам осуществляется с помощью operator()(unsigned, unsigned), иными словами, a(i, j) — ij-элемент матрицы a. Для простоты полагается представление весов в виде double.
  3. Матрица предшественников (параметр шаблона PreviousMatrix), например, Pr. Тогда Pr(i, j) хранит индекс вершины, предшествующей j на пути из вершины i. Таким образом, элементы имеют тип unsigned.
  4. Массив («вектор») весов/расстояний (параметр шаблона WeightVector), доступ к элементам осуществляется с помощью operator[](unsigned), иными словами, d[i] — i-элемент массива d.
  5. Массив предшественников (параметр шаблона Previous). Аналог матрицы предшественников и массива весов.

По ссылке приведён код, где реализованы алгоритмы Ярника-Прима-Дейкстры построения минимального остова («minimal spanning tree»), Дейкстры поиска кратчайших путей от одной вершины до всех остальных, Флойда-Уоршелла поиска кратчайших путей между всеми парами вершин графа, а также приведён пример их использования.

Дополнительная ссылка на код.

Тест

Кроме того, данный код включает тест времени выполнения приведённых алгоритмов, который можно использовать, например, для тестирования различных реализаций матриц. Его точность не очень высока, однако результаты могут представлять определённый интерес. Далее приведён усреднённый (на 4 запусках) результат для двух машин (компилятор Visual C++ 2010):

  1. AMD Phenom2 955 @ 3.2GHz, 880G, 2x 2Gb DDR3-1333 9-9-9-24 — 512Mb IGP UMA.
  2. Intel Celeron U3400 @ 1.07GHz, H55, 4Gb DDR3-800.
Вариант Остов Дейкстра Флойд
AMD 32-bit 23.054с 23.167с 17.873с
AMD 64-bit 21.239с 20.137с 12.822с
Intel 32-bit 34.538с 68.543с 44.223с
Intel 64-bit 28.860с 62.888с 29.882с

Задания

  1. Прочитать и понять приведённый код. Из шести выводимых программой чисел три выводятся без поясняющего текста. Что означают эти три числа? Почему два последних совпадают?
  2. Реализовать алгоритм построения минимального остова Борувки-Краскала.
  3. Модифицировать алгоритм Флойда-Уоршелла для построения матрицы достижимости из матрицы смежности.
  4. Подумать об оптимизации рассмотренных алгоритмов для работы с разряжёнными графами. Разряжёнными называют графы, у которых число рёбер сопоставимо с числом вершин (например, планарные или графы с ограниченной степенью вершин).
Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: