Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

Специальность 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].

Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sx до заданной конечной вершины tx, при условии, что такой путь существует tR(s) (здесь R(s) - множество, достижимое из вершины s) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и х_i - некоторая его вершина, то, двигаясь от s к х_i, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым (> ?) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

1.3 ОПИСАНИЕ МЕТОДА РЕШЕНИЯ ЗАДАЧ

Процедура находит путь минимального веса в графе G = (V, E) заданном весовой матрицей W у которой элемент равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы w_ij неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2 . Процедура использует алгоритм Дейкстры. Для представления веса, равного бесконечности, используется число GM, передаваемое в алгоритм. Это число можно задавать в зависимости от конкретной задачи.

Алгоритм по которому происходит поиск заключается в следующем:

всем вершинам приписывается вес - вещественное число, d(i) := GM для всех вершин кроме вершины с номером u₁ , а d(u₁ ) := 0

всем вершинам приписывается метка m(i) := 0

вершина u₁ объявляется текущей: t := u₁

для всех вершин у которых m(i) равно 0, пересчитываем вес по формуле: d(i) := min{d(i), d(t)+W[t,i]}

среди вершин для которых выполнено m(i) = 0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует, покидаем алгоритм

иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t) := 1)

если t = u₂ , то найден путь веса d(t), покидаем алгоритм

переходим на следующий шаг.

алгоритм дейкстры turbo pascal

1.4 ФУНКЦИОНАЛЬНЫЕ ТЕСТЫ

Задача 1

Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных

Рисунок 5

Представим граф, в виде матрица длин дуг

Таблица1

	X1	X2	X3	X4	X5	X6
x1	?	10	18	7	?	?
x2	10	?	16	9	9	?
x3	?	16	?	?	15	?
x4	7	9	?	?	?	12
x5	?	?	?	?	?	23
x6	?	?	15	?	23	?

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.

Задаем стартовые условия: d(1)=0, d(x)=? Окрашиваем вершину 1, y=1.

Находим ближайшую вершину к окрашенной нами, используя формулу

d(x)=min{d(x);d(y)+a(y,x)}

Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=7. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину.

Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=7. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу, ведущую в эту вершину. Согласно выражению это дуга (1,4)

Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.

d(1)=1 Длина маршрута L=0;

d(2)=1-4-2 Длина маршрута L=16;

d(3)=1-4-2-5-6-3 Длина маршрута L=63;

d(4)=1-4 Длина маршрута L=7;

d(5)=1-4-2-5 Длина маршрута L=25;

d(6)=1-4-2-5-6 Длина маршрута L=48.

Задача 2

Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных

Рисунок 6

Представим граф, в виде матрица длин дуг

Таблица 2

	X1	X2	X3	X4	X5	X6
x1	0	5	3	2	?	?
x2	?	0	1	?	?	?
x3	?	?	0	?	?	1
x4	?	?	?	0	?	3
x5	?	2	?	?	0	?
x6	?	?	?	?	1	0

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.

Задаем стартовые условия: d(1)=0, d(x)=?

Окрашиваем вершину 1, y=1.

Находим ближайшую вершину к окрашенной нами, используя формулу

d(x)=min{d(x); d(y)+a(y,x)}

d(2)=min{8}

d(3)=min{9}

d(4)=min{2}

d(5)=min{6}

d(6)=min{5}

Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=2. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу, ведущую в эту вершину. Согласно выражению это дуга (1,4)

Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.

d(1)=1 Длина маршрута L=0;

d(2)=1-4-6-5-2 Длина маршрута L=8;

d(3)=1-4-6-5-2-3 Длина маршрута L=9;

d(4)=1-4 Длина маршрута L=2;

d(5)=1-4-6-5 Длина маршрута L=6;

d(6)=1-4-6 Длина маршрута L=5.

Задача 3

Дан граф смежности для нахождения минимального пути от вершины 2 до всех остальных.

Рисунок 7

Представим граф, в виде матрица длин дуг.

Таблица3

	X1	X2	X3	X4
x1	0	2	3	3
x2	4	0	5	3
x3	8	4	0	8
x4	1	5	3	0

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 2.

Задаем стартовые условия: d(2)=0, d(x)=?

Окрашиваем вершину 2, y=2.

Находим ближайшую вершину к окрашенной нами, используя формулу

d(x)=min{d(x);d(y)+a(y,x)}

d(1)=min{4}

d(3)=min{7}

d(4)=min{3}

Минимальную длину имеет путь от вершины 2 до вершины 4 d(4)=3. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу, ведущую в эту вершину. Согласно выражению это дуга (2,4)

Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №2 для исходного графа.

d(1)=2-4-1 Длина маршрута L=4;

d(2)=2 Длина маршрута L=0;

d(3)=2-4-1-3 Длина маршрута L=7;

d(4)=2-4 Длина маршрута L=3.



ГЛАВА 2. МОДЕЛИРОВАНИЕ, АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ МЕТОДА

2.1 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ

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

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

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

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

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

Обозначения:

w[ij] - вес (длина) ребра ij.

a - начальная вершина.

U - множество посещенных вершин.

d[u] - по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u.

p[u] - по окончании работы алгоритма содержит кратчайший путь из a в u.

Пусть l(v) - длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). Первой посещается вершина a. В этот момент d(a)=l(a)=0.

2 Шаг. Пускай мы выбрали для посещения вершину z ? a. Докажем, что в этот момент d(z) = l(z). Для начала отметим, что для любой вершины v, всегда выполняется d(v)?l(v) (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P - кратчайший путь из a в z, y - первая непосещённая вершина на P, x - предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно, l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y) (если существует k, такое что l(k) + w(ky) < l(x) + w(xy) то x не принадлежит P). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть d(z)?d(y)=l(y)?l(z). Комбинируя это с d(z) ?l(z), имеем d(z)=l(z), что и требовалось доказать.

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

3.2 ВХОДНЫЕ - ВЫХОДНЫЕ ДАННЫЕ ЗАДАЧИ

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

Выходными данными являются оптимальный вектор и значение целевой функции , которые выводятся также в компоненту.

2.3 БЛОК - СХЕМА РЕШЕНИЯ ЗАДАЧИ

Рисунок 8

2.4 ТЕСТИРОВАНИЕ

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

Задача 1

Дана матрица смежности для нахождения минимального пути от вершины 1 до всех остальных

Таблица 4

	X1	X2	X3	X4	X5	X6
x1	?	10	18	7	?	?
x2	10	?	16	9	9	?
x3	?	16	?	?	15	?
x4	7	9	?	?	?	12
x5	?	?	?	?	?	23
x6	?	?	15	?	23	?

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.

Задаем стартовые условия: d(1)=0, d(x)=? Окрашиваем вершину 1, y=1.

Находим ближайшую вершину к окрашенной нами, используя формулу

d(x)=min{d(x);d(y)+a(y,x)}

после решения ручным методом мы получили следующие пути и вес маршрутов.

d(1)=1 Длина маршрута L=0;

d(2)=1-4-2 Длина маршрута L=16;

d(3)=1-4-2-5-6-3 Длина маршрута L=63;

d(4)=1-4 Длина маршрута L=7;

d(5)=1-4-2-5 Длина маршрута L=25;

d(6)=1-4-2-5-6 Длина маршрута L=48.

Рисунок 9

Задача 2

Дана матрица смежности для нахождения минимального пути от вершины 1 до всех остальных

Таблица 5

	X1	X2	X3	X4	X5	X6
x1	0	5	3	2	?	?
x2	?	0	1	?	?	?
x3	?	?	0	?	?	1
x4	?	?	?	0	?	3
x5	?	2	?	?	0	?
x6	?	?	?	?	1	0

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.

Задаем стартовые условия: d(1)=0, d(x)=? Окрашиваем вершину 1, y=1.

Находим ближайшую вершину к окрашенной нами, используя формулу

d(x)=min{d(x);d(y)+a(y,x)}

после решения ручным методом мы получили следующие пути и вес маршрутов.

d(1)=1 Длина маршрута L=0;

d(2)=1-4-6-5-2 Длина маршрута L=8;

d(3)=1-4-6-5-2-3 Длина маршрута L=9;

d(4)=1-4 Длина маршрута L=2;

d(5)=1-4-6-5 Длина маршрута L=6;

d(6)=1-4-6 Длина маршрута L=5.

Рисунок10

Задача 3

Дана матрица смежности для нахождения минимального пути от вершины 1 до всех остальных

Таблица 6

	X1	X2	X3	X4
x1	0	2	3	3
x2	4	0	5	3
x3	8	4	0	8
x4	1	5	3	0

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 2.

Задаем стартовые условия: d(2)=0, d(x)=? Окрашиваем вершину 2, y=2.

Находим ближайшую вершину к окрашенной нами, используя формулу

d(x)=min{d(x);d(y)+a(y,x)}

после решения ручным методом мы получили следующие пути и вес маршрутов.

d(1)=2-4-1 Длина маршрута L=4;

d(2)=2 Длина маршрута L=0;

d(3)=2-4-1-3 Длина маршрута L=7;

d(4)=2-4 Длина маршрута L=3.

Рисунок 11

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



ГЛАВА 3. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

3.1 ДИАЛОГ С ПОЛЬЗОВАТЕЛЕМ

При открытии программы открывается главное окно, где и происходит ввод количества вершин.

Рисунок12

Вспомогательное окно ввода количества вершин, если в главном окне было введено некоретное число, такое как буквы или большое число вершин (в программе используется максимум 15 вершин)

Рисунок13

Окно вывода результата действий. После подсчета окно открывается автоматически. В этом окне можно производить сохранение результата в формате (.txt)



Рисунок14

Окно справка, краткое описание действия программы, так же ФИО программиста

Рисунок15

Рисунок16



ЗАКЛЮЧЕНИЕ

Для достижения поставленной цели потребовалось реализовать алгоритмы Дейкстры на языке программирования Turbo Pascal. При использовании среды разработки Borland Delphi. В результате созданной программы была получена возможность нахождения минимального пути в графе. Сложность поставленной задачи обуславливается тем, что для поиска кратчайшего пути необходимо наличие достаточно большого количества достоверной информации, что не всегда представляется возможным. Размерность массива, определяющего поиск может быть слишком большой, что потребует больших затрат времени, не позволяя решать задачу в реальном режиме времени.

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

Проверка качества разрабатываемого продукта была проведена с помощью «Сборник заданий по дискретной математике» Павленкова Е.В., Чекмарев Д.Т. откуда были взяты одиннадцать задач и ответы к ним. Решив эти задачи с помощью разрабатываемого продукта, было получено 7 совпадений, таким образом, коэффициент качества составил .

В ходе курсового проекта были выполнены все поставленные задачи, была достигнута основная цель.



СПИСОК ЛИТЕРАТУРЫ

1. Алгоритм Дейкстры //Википедия. [Электронный ресурс]. URL: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

2. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. //Интернет университет информационных технологий. [Электронный ресурс]. URL: http://www.intuit.ru/department/algorithms/gaa/15/

3. Альфред В. Ахо, Джон Э. Хопкрофт, Структуры данных и алгоритмы. изд. дом «Вильямс», Москва, 2000. 118с.

4. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку. М.: «Вильямс», 2006. 189--195 с.

5. Голицына О. Л., Попов И. И. Основы алгоритмизации и программирования: Учебное пособие/ 2-е издание., М.: ФОРУМ. 2006.432 с. (Профессиональное образование).

6. Кузнецов Ю. Н., Кузубов В. И., Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. М.; 1980, 300 с. (Высшая школа)

7. Лавров С.С. Программирование. Математические основы, средства, теория. СПб.: БХВ, Петербург, 2001. 319 с.

8. Павленкова Е.В., Чекмарев Д.Т. СБОРНИК ЗАДАНИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ. Учебно-методическое пособие. Нижний Новгород: Нижегородский госуниверситет, 2012. 68 с.

9. Решение онлайн//Поиск оптимального пути (метод Дейкстры) [Электронный ресурс]. URL: http://uchimatchast.ru/aplication/dejkstra0.php

10. Шпак Ю. А. Delphi 7 на примерах/Под ред. Ю. С. Ковтанюка К.: Издательство Юниор, 2003. 384 с.

Размещено на Allbest.ru