Нахождение кратчайших путей в графе Алгоритм Йена

Содержание

1. Введение

В настоящее время все более актуальными становятся задачи оптимизации, поиска, реализации распределенных и (или) параллельных систем. Многие из них легко реализуемы простыми математическими методами, но некоторые задачи требуют к себе особого подхода. Эти задачи либо не разрешимы простыми методами, либо их решение потребует значительного времени и объема ресурсов. Для решения подобного рода задач существуют особые методы и алгоритмы. К их числу относится алгоритм нахождения k кратчайших путей в графе.

Для реализации решения данной задачи используется алгоритм Дейкстры – для нахождения одного кратчайшего пути между двумя точками в графе, – и алгоритм Йена – для нахождения заданного числа кратчайших путей в графе.

В исследовании этих двух алгоритмов собственно и состоит задача курсовой работы.

2. Логико-функциональная модель алгоритма

2.1. Теоретические сведения

Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения — наиболее часто встречаемые.

Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

· V это множество вершин или узлов,

· E это множество рёбер – связей между парами вершин.

V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.

СтепеньюdegV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Задачу составления алгоритма нахождения k кратчайших путей в графе условно можно разбить на две подзадачи:

1) Нахождение одного кратчайшего пути между двумя точками (реализуется алгоритм Дейкстры)

2) Нахождение k кратчайших путей между двумя точками (реализуется алгоритм Йена)

2.2. Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием “кратчайший путь — первый” (Shortest Path First)

Объяснение:

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

2.3. Алгоритм Йена

Этот алгоритм предполагает, что мы умеем находить один кратчайший путь в графе.

Делается это так: Будем вести список кандидатов в кратчайшие пути. Hаходится первый кратчайший путь. Так как все другие пути не должны совпадать с первым путем, то эти остальные пути не содержат как минимум одно из ребер первого пути. Поэтому, выкидываем по одному ребру из первого пути и находим кратчайшие пути в получаемых графах. Hайденные пути (с пометкой о том, какое ребро было выкинуто) добавляем в список кандидатов. Из списка кандидатов выбираем самый короткий путь - это второй самый короткий путь.

Далее находим следующий самый короткий путь аналогично. При нахождении каждого самого короткого пути в список кандидатов добавляется не более N новых путей (на самом деле конечно меньше).

При удалении ребра нахождение кратчайшего пути в полученном графе производится за линейное время. Для этого в исходном графе алгоритм Дейкстры запускается как от начальной, так и от конечной вершины. При удалении одного ребра кратчайший путь в новом графе ищется с использованием деревьев, полученных для исходного графа.

3. Блок-схема алгоритма

4. Анализ сложности алгоритма

Анализ сложности и трудоемкости алгоритма заключается в выявлении того, насколько эффективно работает алгоритм и насколько сильно загружается процессор. Основным критерием в этом плане является скорость выполнения алгоритма.

Скорость выполнения можно легко измерить, используя стандартные функции языка PHP, на котором был написан алгоритм. При этом будем циклически высчитывать время, затраченное на обработку графов размерности от 3 до 19 вершин. См. рис. 1

Рис. 1 – Зависимость времени выполнения tот числа вершин n

Несложно заметить, что функция имеет вид параболы. Это означает, что с увеличением размера графа довольно резко возрастает и время выполнения. Таким образом, алгоритм будет работать эффективно с графами размером до 20 вершин. Что же касается графов с большим размером, то, к примеру, граф размером 30 вершин будет обрабатываться 195.74 секунд, то есть немногим больше 3 минут. Это не очень удобно, однако стоит заметить, что данный алгоритм тестировался на компьютере с тактовой частотой 2.02 ГГц, что не так уж много по сегодняшним меркам.

5. Разработка программы

Как уже говорилось, задача нахождения k кратчайших путей в графе состоит из двух алгоритмов: алгоритма Дейкстры и алгоритма Йена

5.1. Реализация алгоритма Дейкстры

Прежде всего необходимо проинициализировать матрицу данных. Матрица данных представляет собой двухмерный массив, значениями которого являются длины ребер, которые соединяют точки, являющиеся в матрице координатами по x и по y. На примере рассмотрен такой граф:

$matrix = array(

array(0, 7, 9, 0, 0, 14),

array(0, 0,10,15, 0, 0),

array(0, 0, 0,11, 0, 2),

array(0, 0, 0, 0, 6, 0),

array(0, 0, 0, 0, 0, 9),

array(0, 0, 0, 0, 0, 0)

);

Таким образом видно, что вес ребра, соединяющего, к примеру, 2-ю и 5-ю точки будет соответствовать значению 2-го ряда и 5-го столбца (или 5-го ряда и 2-го столбца) в матрице.

Продолжаем инициализацию: переменная $start хранит номер исходной точки (начиная с нуля), переменная $end – конечной, одномерный массив $dist – кратчайшие расстояния от исходной точки до всех остальных, а двухмерный массив $way– кратчайшие пути в графе.

Всем элементам массива $dist (кроме $dist[$start]) присваивается значение, которое будет заведомо больше длины любого пути в графе. В программе это число 1000. Элементу $dist[$start] присваивается значение 0. Также присваиваем значение первому шагу в массиве путей: $way[$start][0] = $start. Все это имеет такой вид:

for ($i = 0; $i < MAX_NODES; $i++)

{

if ($i == $start)

$dist[$i] = 0;

else

$dist[$i] = INFINITY;

}

$way[$start][] = $start;

Далее начинается основная часть алгоритма. Проходим в цикле по каждой точке графа: находим точку с минимальным значением расстояния. Дляэтогоиспользуемфункцию minDist:

function minDist($dist)

{

global $checked;

$min_v = INFINITY;

for ($i = 0; $i < MAX_NODES; $i++)

{

if (!isset($checked[$i]) && $dist[$i] < $min_v)

{

$min = $i;

$min_v = $dist[$i];

}

}

$checked[$min] = true;

return $min;

}

Потом опять же в цикле просматриваем связи найденной точки с остальными точками в графе, и, если сумма цены ребра, соединяющего найденную точку с данной и расстояния от исходной точки до найденной меньше, чем расстояние от исходной точки до данной, то мы выполняем замену. Также при этом сохраняем значение пункта пути – массива $way:

for ($i = 0; $i < MAX_NODES; $i++)

{

$min = minDist($dist);

for ($j = 0; $j < MAX_NODES; $j++)

{

if ($dist[$min] + $matrix[$min][$j] < $dist[$j])

{

$dist[$j] = $dist[$min] + $matrix[$min][$j];

$way[$j] = $way[$min];

$way[$j][] = $j;

}

if ($dist[$min] + $matrix[$j][$min] < $dist[$j])

{

$dist[$j] = $dist[$min] + $matrix[$j][$min];

$way[$j] = $way[$min];

$way[$j][] = $j;

}

}

}

В результате получаем массив минимальных расстояний - $dist и двухмерный массив кратчайших путей - $way.

5.2. Реализация алгоритма Йена

Для нахождения k кратчайших путей в графе используется рекурсивная функция findWays, которая в качестве параметров принимает матрицу данных, номера исходной и конечной вершин. Алгоритм этой функции таков: выполняется поиск одного кратчайшего пути графа, проверяется, есть ли найденный путь в массиве путей $ways и, если нет – сохраняем путь и в цикле убираем по одному ребру в найденном пути и вызываем функцию findWays, передавая ей уже обновленную матрицу данных:

function findWays($matrix, $start, $end)

{

global $ways;

$res = findShortestWay($matrix, $start, $end);

if ($res != null && !in_array($res, $ways))

{

$ways[] = array();

$ways[count($ways)-1][1] = $res[1];

$ways[count($ways)-1][0] = $res[0];

for ($i = 0; $i < count($res[1])-1; $i++)

{

$invalid_matrix = $matrix;

$invalid_matrix[$res[1][$i]][$res[1][$i+1]] = INFINITY;

$invalid_matrix[$res[1][$i+1]][$res[1][$i]] = INFINITY;

findWays($invalid_matrix, $start, $end);

}

}

}

Стоит заметить, что массив $ways является трехмерным – первый ключ соответствует номеру пути, второй указывает на а) длину пути б) массив вершин пути

После этого выполняется сортировка полученного массива $ways по возрастанию по длине пути.

for ($i = 0; $i < count($ways)-1; $i++)

{

for ($j = $i+1; $j < count($ways); $j++)

{

if ($ways[$i][0] > $ways[$j][0])

{

$buf = $ways[$i];

$ways[$i] = $ways[$j];

$ways[$j] =$buf;

}

}

}

После возврата первых k элементов массива $ways наш алгоритм можно считать реализованным.

6. Заключение

Хотя поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков.

Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы.