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

Содержание

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 | — размером графа.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--