Нахождение минимального пути в графе (алгоритм Дейкстры)

Теория графов и её применения. Разработка программного продукта для решения задач нахождения минимального пути. Анализ надежности и качества ПП "метода Дейкстры". Математическая модель задачи. Алгоритмы Дейкстры на языке программирования Turbo Pascal.
Краткое сожержание материала:

Размещено на

Размещено на

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сахалинский государственный университет»

Сахалинский государственный колледж бизнеса и информатики

Курсовая работа

Тема: Нахождение минимального пути в графе (алгоритм Дейкстры)

Студента: Курта Евгения Андреевича

Специальность 230105.51

«Программное обеспечение вычислительной техники и автоматизированных систем»

Курс 4, группа П-401

Форма обучения: очная.

Научный руководитель:

Сливчак Светлана Ивановна

Южно-Сахалинск 2013г.



ВВЕДЕНИЕ

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

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторика, Алгоритм на графах, изобретён нидерландским ученым Э. Дейкстрой в 1959 год его алгоритм был рассчитан для нахождения минимального пути положительных чисел, и был назван в его честь алгоритм Дейкстры. Графы стали использоваться при построении схем электрических цепей и молекулярных схем.

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

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

Задачи курсовой работы:

· Изучить предметную область

· Определить входные, выходные данные

· Определить метод решения нахождения минимального пути

· Выполнить структурное проектирование задачи в виде блок схемы

· Спроектировать интерфейсные формы ПП «метода Дейкстры»

· Разработать ПП «метода Дейкстры»

· Произвести анализ надежности и качества ПП «метода Дейкстры»

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



ГЛАВА 1. НАХОЖДЕНИЯ МИНИМАЛЬНОГО ПУТИ В ГРАФЕ (АЛГОРИТМ ДЕЙКСТРЫ)

1.1 ЭКОНОМИЧЕСКАЯ СУЩНОСТЬ ЗАДАЧИ

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

Для примера. При эвакуации населения из очагов бедствия оптимальные маршруты до пунктов сбора транспорта для каждой группы людей (дом, улица, школа и т. Д )в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.

Так же в протоколе OSPF используется итеративный алгоритм Дейкстры. Каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг-до следующего маршрутизатора, в соответствии с принципом одношаговой маршрутизации. Данные об этом шаге и попадают в таблицу маршрутизации. Если несколько маршрутов имеют одинаковую метрику до сети назначения, то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов."

1.2 ПОСТАНОВКА ЗАДАЧИ

Постановка задачи на максимум выглядит следующим образом:

Граф G задается множеством вершин х₁, х₂,…, х_n. (которое обозначается через Х) и множеством линий (ребер) а₁, а₂,…, а_m. (которое обозначается символом А), соединяющих между собой все или часть этих вершин в соответствии с рисунком 1. Таким образом, граф G полностью задается (и обозначается) парой (Х, А).

Рисунок 1 - Граф G

Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом в соответствии с рисунком 2.

Рисунок 2 - Ориентированный граф

Например, если дорога имеет не двух -, а одностороннее движение то направление этого движения будет показано стрелкой. Если ребра не имеют ориентации, то граф называется неориентированным в соответствии с рисунком 3.

Рисунок 3 - Неориентированный граф

В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин(т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рисунке 2 обозначение (х₁, х₃) относится к дуге а₁. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рисунке 2: Г (х₁)={х₂, х₃}, т.е. вершины х₂ и х₃ являются конечными вершинами дуг, у которых начальной вершиной является вершина х₁.

На рисунке 3: Г (х₁)={х₂, х₄, х₅}, (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.) Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Так, на рисунке 4 последовательности дуг являются путями.

а₆, а₅, а₉, а₈. (1)

а₁, а₆, а₅, а₉. (2)

а₁, а₆, а₅, а₉, а₁₀, а₆. (3)

Рисунок 4 - Граф H

Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т. к. дуга а₆ в нем используется дважды. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) - нет. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер д₁, д₂,…, д_q, в которой каждое ребро а_q за исключением первого и последнего ребер, связано с ребрами а_i-1 и а_i+1 своими концевыми вершинами. Последовательности дуг:

д₂, д₄, д₈, д₁₀ (4)

д₂, д₇, д₈, д₄, д₃, (5)

д₁₀, д₇, д₄, д₈, д₇, д₂. (6)

В графе, изображенном на рисунок, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х₂, х₅, х₄, х₃, х₅, х₆. Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом с взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. При рассмотрении пути µ представленного последовательностью дуг (д₁, д₂,…, д_q), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.

Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости длины), задаваемые матрицей С = [c_ij].

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