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

Содержание

1. Введение……………………………………………………………. 2. Логико-функциональная модель алгоритма……………………… 2.1. Теоретические сведения………………………………………... 2.2. Алгоритм Дейкстры…………………………………………….. 2.3. Алгоритм Йена………………………………………………….. 3. Блок-схема алгоритма……………………………………………... 4. Анализ сложности алгоритма……………………………………... 4. Разработка программы…………………………………………….. 4.1. Реализация алгоритма Дейкстры……………………………… 4.2. Реализация алгоритма Йена……………………………………. 5. Заключение………………………………………………………….

2 3 3 5 6 7 10 12 12 16 18

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 с этим соседом. Если полученная длина мень

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать