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

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

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

Ребро называется петлёй, если его концы совпадают, то есть 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. На примере рассмотрен такой граф: