Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

• Введение
• 1. Анализ предметной области
• 1.1 Основные определения
• 1.2 Компьютерные средства для реализации задачи
• 1.3 Цель и задачи курсовой работы
• 2. Анализ задачи и методов ее решения
• 2.1 Задача поиска выделенного кратчайшего пути
• 2.2 Алгоритм Дейкстры
• 2.3 Задача поиска всех кратчайших путей
• 2.4 Алгоритм Флойда
• 3. Разработка программы
• 3.1 Характеристика программы и системные требования
• 3.2 Описание модульной структуры разработанной программы
• 3.3 Описание диалога с пользователем
• 3.4 Контрольный пример
• Заключение
• Список литературы

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

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

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

Курсовая работа носит учебный характер. В ходе её выполнения реализуются имеющиеся знания из курса дискретной математики по решению задачи в программной интерпретации на языке программирования Deplhi 7.0, формируются навыки по определению входных-выходных данных, анализ предметной области, выбор методов и средств для решения поставленной задачи. Также приобретаются навыки по разработке алгоритма по решения задачи. А знание компьютера и наличие опыта в программировании в наше время особенно приветствуется в сфере информационных технологий.

1. Анализ предметной области

1.1 Основные определения

Графом G= (X, U) будем называть совокупность двух конечных множеств; множества вершин X={x,…x} и множества ребер (дуг) U={u… u}, состоящего из некоторых пар элементов (x, x) множества X. Геометрически граф может быть представлен в виде рисунка, в котором вершинам соответствуют точки, а ребрам линии, соединяющие все или некоторые из этих точек. Граф называется помеченным, если его вершинам приписаны некоторые метки, например номера.

Если пары вершин (x, x) в множестве U являются неупорядоченными (т.е., порядок соединения вершин несущественен), то граф называется неориентированным (неорграфом), а пары (x, x) — ребрами этого графа (рисунок 1).

Рисунок 1

дискретная математика ориентированный граф При этом вершины x, x называют концами (концевыми вершинами) ребра. В данном случае также говорят, что ребро (x, x) — соединяет вершины xи x.

Если пары вершин (x, x) в множестве U являются упорядоченными (т.е., порядок соединения вершин существенен), то граф называется ориентированным (орграфом), а пары (x, x) — дугами (рисунок 2).

Рисунок 2

При этом x — начало (начальная вершина) дуги, x — конец (конечная вершина) дуги. Говорят также, что дуга исходит из вершины xи заходит в вершину x. Заметим, что и — это различные дуги в графе. При изображении орграфа дуги обозначаются стрелками, указывающими их ориентацию (направление). Пара вершин (x, x) в графе может соединяться двумя или более ребрами (дугами одного направления).

Отметим, что любой неориентированный граф можно представить в виде орграфа путем замены каждого его ребра двумя противоположно направленными дугами. [1]

Иногда дугам графа G сопоставляются (приписываются) числа — дуге (x, x) ставится в соответствие некоторое число с, называемое весом, или длиной, или стоимостью (ценой) дуги. Тогда граф G называется графом со взвешенным дугами. Иногда веса (числа v) приписываются вершинам x графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным.

Петлей называется дуга, начальная и конечна вершины которой совпадают. Примером петли является дуга u на рисунке 1. [2]

Последовательность ребер неорграфа (x, x),…, (x, x), в которой конец каждого предыдущего ребра совпадает с началом следующего, называется маршрутом, соединяющим вершины x и x. Аналогом маршрута для орграфа является ориентированный маршрут из x в x, представляющий собой последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей. При этом x и xназываются начальной и конечной вершинами маршрута. Если любые две вершины графа соединены маршрутом, то граф называется связным.

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

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

Число дуг, исходящих из вершины x ориентированного графа, называется полустепенью исхода вершины x и обозначается (x). Число дуг, заходящих в вершину x, называется полустепенью захода вершины x и обозначается (x). [1]

Ранее мы рассмотрели графические способы задания графа. Существуют и другие способы определения графа, например с помощью матрицы смежности. Пусть дан граф G (рисунок 3)

Рисунок 3 — Граф G

Матрицей смежности неориентированного графа G= (X, U) с n вершинами называется квадратная матрица, А порядка n, элементы которой определяются следующим образом:

Для ориентированного графа:

Следовательно, матрица смежности графа, изображенного на рисунку 3 имеет вид, в противном случае Рисунок 4 — Матрица смежности графа G

Петлям в матрице смежности соответствуют элементы, расположенные на главной диагонали. Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки x матрицы дает полустепень исхода вершины x, а сумма элементов столбца x — полустепень захода вершины x. Множество столбцов, имеющих 1 в строке x, есть множество Г (x), а множество строк, которые имеют 1 в столбце x, совпадает с множеством Г (x). [2]

1.2 Компьютерные средства для реализации задачи

1) Turbo Pascal — интегрированная среда разработки программного обеспечения для платформ DOS и Windows 3. x и язык программирования в этой среде, диалект языка Паскаль от фирмы Borland. Особенностями языка являются строгая типизация и наличие средств структурного (процедурного) программирования. Паскаль был одним из первых таких языков. По мнению Н. Вирта, язык должен способствовать дисциплинированию программирования, поэтому, наряду со строгой типизацией, в Паскале сведены к минимуму возможные синтаксические неоднозначности, а сам синтаксис интуитивно понятен даже при первом знакомстве с языком.

В настоящий момент пользуются популярностью такие версии языка как Turbo Pascal, Free Pascal и GNU Pascal. Продолжает использоваться и Borland Pascal. Развитием языка Borland Pascal является Object Pascal — версия языка Паскаль расширенная средствами объектно-ориентированного программирования. Последние версии Borland Pascal лежат в основе среды программирования Delphi.

2) Язык программирования Delphi

Delphi — это потомок Турбо Паскаля, который был выпущен для операционной системы CP/M в 1983 году. В феврале 1994 года Турбо Паскаль был перенесен на операционную систему MS-DOS.

На раннем этапе развития компьютеров IBM PC, Турбо Паскаль являлся одним из наиболее популярных языков разработки программного обеспечения — главным образом потому, что это было вполне серьезный компилятор, который, включая компилятор, редактор и все остальное, стоил всего $ 19.95 и работал на машине с 64 Kb оперативной памяти.

Под Windows — Турбо Паскаль был перенесен фирмой Borland в 1990 году. А самая последняя версия Borland Pascal 7.0 (имеющая теперь такое название), не считая Delphi, вышла в свет в 1992 году.

Разработка Delphi началась в 1993 году. После проведения beta-тестирования Delphi показали на «Software Development '95». И 14 февраля 1995 года официально объявили о ее продаже в США. В торговлю Delphi попала спустя 14 дней, 28 февраля 1995 года. [4]

3). Язык программирования C++

C++ был разработан в 1980 году в компании Bell. Он считается наиболее подходящим языком для обновления систем, написанных на языке С.

Изначально C++ был разработан, чтобы автору и его друзьям не приходилось программировать на ассемблере, C или других современных языках высокого уровня. Основным его предназначением было сделать написание хороших программ более простым и приятным для отдельного программиста. Плана разработки C++ на бумаге никогда не было; проект, документация и реализация двигались одновременно. Разумеется, внешний интерфейс C++ был написан на C++. Никогда не существовало «Проекта C++» и «Комитета по разработке C++». Поэтому C++ развивался и продолжает развиваться во всех направлениях, чтобы справляться со сложностями, с которыми сталкиваются пользователи, а также в процессе дискуссий автора с его друзьями и коллегами" .

В языке С++ полностью поддерживаются принципы объектно-ориентированного программирования, включая три кита, на которых оно стоит: инкапсуляцию, наследование и полиморфизм. Инкапсуляция в С++ поддерживается посредством создания нестандартных (пользовательских) типов данных, называемых классами. Язык С++ поддерживает наследование. Это значит, что можно объявить новый тип данных (класс), который является расширением существующего. Хотя язык С++ справедливо называют продолжением С и любая работоспособная программа на языке С будет поддерживаться компилятором С++, при переходе от С к С++ был сделан весьма существенный скачок. Язык С++ выигрывал от своего родства с языком С в течение многих лет, поскольку многие программисты обнаружили, что для того, чтобы в полной мере воспользоваться преимуществами языка С++, им нужно отказаться от некоторых своих прежних знаний и приобрести новые, а именно: изучить новый способ концептуальности и решения проблем программирования. Перед тем как начинать осваивать С++, Страуструп и большинство других программистов, использующих С++ считают изучение языка С необязательным. C++ в настоящее время считается господствующим языком, используемым для разработки коммерческих продуктов, 90% игр пишутся на С++ с применением DirectX. Проанализировав и сравнив все рассмотренные языки программирования, для решения своей задачи мной был выбран Delphi 7., т.к. для меня он является наиболее простым в обращении, имеет наиболее понятный интерфейс и простой синтаксис написания программ. [5]

1.3 Цель и задачи курсовой работы

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

Задачи курсовой работы: определение входных данных; анализ задачи и выбор методов её решения; разработка алгоритма для решения поставленной задачи; разработка программы на одном из языков высокого уровня;

2. Анализ задачи и методов ее решения

2.1 Задача поиска выделенного кратчайшего пути

Каждой дуге (x, y) исходного графа G поставим в соответствие число a (x, y). Если в графе G отсутствует некоторая дуга (x, y), положим a (x, y) =. Будем называть число a (x, y) длиной дуги (x, y), хотя a (x, y) можно также интерпретировать как соответствующие затраты или соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь.

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

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

Предположим, что вы хотите проехать из Бостона в Лос-Анджелес, используя магистральные шоссейные дороги, соединяющие различные штаты. Как выбрать кратчайший маршрут?

Постройте граф, вершины которого соответствуют точкам соединения рассматриваемых дорог. Пусть каждая дуга графа соответствует шоссейной дороге, соединяющие пункты, представленные соответственными вершинами. Пусть длина пути определятся длиной (в километрах) соответствующего участка дороги. Теперь задача поиска оптимального маршрута движения между Бостоном и Лос-Анджелесом может быть сведена к задаче отыскания в построенном графе кратчайшего пути между вершинами, соответствующими Бостону, откуда вы начинаете путешествие, и Лос-Анджелесу, где ваше путешествие заканчивается.

2.2 Алгоритм Дейкстры

Для нахождения кратчайшего пути между двумя конкретными вершинами s и t широко применяется алгоритм Дейкстры. Далее рассмотрим шаги данного алгоритма.

Шаг 1. перед началом выполнения алгоритма дуги не окрашены. Каждой вершине в ходе выполнения алгоритма присваивается число d (x), равное длине кратчайшего пути из s в x, включающего только окрашенные вершины.

Положить d (s) =0 и d (x) = для всех x, отличных от s. Окрасить вершину s и положить у=s (y-последняя из окрашенных вершин).

Шаг 2. Для каждой неокрашенной вершины x следующим образом пересчитать величину d (x):

(1)

Если d (x) = для всех неокрашенных вершин x, закончить процедуру алгоритма: в исходном графе отсутствуют пути из вершины s в неокрашенные вершины. В противном случае окрасить ту из вершин x, для которой величина d (x) является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на данном шаге вершину х (для этой дуги достигался минимум в соответствии с выражением (1)). Положить y=x.

Шаг 3. Если y=t, закончить процедуру: кратчайший путь из вершины s в вершину t найден (это единственный путь из s в t, составленный из окрашенных дуг). В противном случае перейти к шагу 2.

Отметим, что каждый раз, когда окрашивается некоторая вершина (не считая вершины s), окрашивается и некоторая дуга, заходящая в данную вершину. Таким образом, на любом этапе алгоритма Дейкстры в каждую вершину заходит не более чем одна окрашенная дуга. Кроме того, окрашенные дуги не могут образовывать в исходном графе цикл, так как в алгоритме не может окрашиваться дуга, концевые вершины которой уже окрашены. Следовательно, можно сделать вывод о том, что окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в вершине s. Это дерево называется ориентированным деревом кратчайших путей. Единственный путь от вершины s до любой вершины x, принадлежащей дереву кратчайших путей, является кратчайшим путем между указанными вершинами.

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

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

Если бы мы хотели определить кратчайшие пути из вершины s во все вершины исходного графа, то процедуру наращивания дерева следовало бы продолжить до тех пор, пока все вершины графа не были бы включены в ориентированное дерево кратчайших путей. При этом для исходного графа было бы получено покрывающее ориентированное дерево (при условии, что в этом графе содержится хотя бы одно такое дерево). Итак, для того, чтобы описанный выше алгоритм позволял получать дерево кратчайших путей от вершины s до всех остальных вершин, его третий шаг должен быть скорректирован следующим образом: если все вершины оказываются окрашенными, закончить процедуру (для любой вершины x имеется единственный путь из s в x, состоящий из окрашенных дуг, и этот путь является кратчайшим путем между соответствующими вершинами); в противном случае перейти к шагу 2.

2.3 Задача поиска всех кратчайших путей

В предыдущем пункте была рассмотрена задача поиска кратчайшего пути между двумя конкретными вершинами s и t. В данном разделе будет изложена задача поиска в графе кратчайшего пути между всеми парами вершин.

Рассмотрим пример данной задачи из сферы деятельности человека. Предположим, что авиакомпания, должна для многочисленных пассажиров ежедневно разрабатывать маршруты полетов между различными городами. Эта авиакомпания в целях экономии своих затрат стремится предоставлять пассажирам наиболее короткие маршруты. Поэтому ей хотелось бы предоставлять пассажирам наиболее короткие маршруты. Очевидно, ей хотелось бы заранее знать кратчайшие маршруты между каждой парой городов США, если, например, речь идет о полетах в пределах США.

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

В этой курсовой работе мы рассмотрим алгоритм Флойда для нахождения кратчайших путей между всеми парами вершин графа. [6]

2.4 Алгоритм Флойда

Алгоритм Флойда — это алгоритм поиска кратчайших путей между всеми вершинами графа.

Пусть дан взвешенный орграф с n вершинами и матрицей весов W. Каждый элемент матрицы весов w равен весу дуги (если такой дуги нет, то w), а w=0 .

Предположим, что граф не содержит контуров отрицательной длины. Пронумеруем вершины графа от 1 до n. Обозначим W матрицу с элементами w, каждый из которых равен длине кратчайшего пути из вершины i в вершину j, который может содержать в качестве промежуточных вершин только первые k вершин графа. Если такого пути не существует, то w=. W=W. По матрице W вычисляется матрица W, содержащая кратчайшие пути между всеми вершинами графа. Элементы матрицы W на k-й итерации вычисляются следующим образом:

w=min, (2)

где w-длина кратчайшего пути из вершины i в вершину k, в которой в качестве промежуточных используются первые k-1 вершины графа.

Для того, чтобы по окончании работы алгоритма можно было быстро построить кратчайший путь, на каждой итерации вместе с матрицей Wстроится матрица P, каждый элемент которой p равен номеру вершины, предшествующей вершине j в текущем ij пути.

На текущей итерации

p, и (3)

p= (4)

Номера вершин, включаемых в кратчайший путь, определяются следующим образом: и т. д.

Основные шаги алгоритма:

1. Пронумеровать вершины графа целыми числами k=0. Определить матрицу W. Определить матрицу P, p=i,, i, j=1. n и p=0, =1. n.

2. Если k=n, работа алгоритма закончена (W-эта матрица весов кратчайших путей между всеми парами вершин графа, определяемых с помощью матрицы P). Если kn, то k=k+1, переход к шагу 3.

3. Вычислить для всех i, j=1…n элементы w=min. Если <, то p=p. Иначе p.

4. Если для некоторого 1 элемент с, то в графе имеется контур отрицательной длины и работа алгоритма завершается. Иначе перейти к шагу 2. [1]

3. Разработка программы

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

3.1 Характеристика программы и системные требования

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

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

Для корректной работы программы необходимы следующие системные требования:

Microsoft windows XP и выше

Intel Pentium ® D 2.80 GHz и выше

ОЗУ 512 МБ

видеокарта: интегрированная NVIDIA GeForce 7300 GS и выше

3.2 Описание модульной структуры разработанной программы

Модулем называется функционально законченная часть программы; критерием для формирования модуля является возможность формулировки назначения модуля в виде одного простого предложения в повелительном наклонении без слов типа: если, то, иначе.

Существуют 4 вида модульных структур: модульно-последовательная, монолитно-модульная, модульно-иерархическая и модульно-хаотическая.

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

Разобьем нашу программу на 4 модуля: модуль ввода начальных данных (приложение А), модуль построения графиков функций (приложение Б), модуль нахождения и уточнения корней уравнений (приложение В) и модуль справки (приложение Г).

Модульная структура программы будет иметь следующий вид:

Рисунок 5 — Схема модульной структуры программы.

Рассчитаем силу связности (SS) и силу сцепления (SC) для полученной модульной структуры.

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

Определим силу сцепления каждого из модулей.

Для модуля диалога с пользователем сила связности SC равна 4, так как данный модуль явно управляет работой остальных модулей.

Для модулей ввода исходных данных, главных процедур и расчетного модуля сила сцепления SC равна 9, так как они поочередно прямо ссылаются на содержание предыдущего.

Для модуля справки о программе сила сцепления SC равна 1, так как входные параметры вызываемого модуля — простые типы данных.

3.3 Описание диалога с пользователем

При запуске программы Kurs_rab. exe пользователь видит главное окно программы. На панели меню имеются вкладки «Файл», «Правка», «Сервис», «Помощь». Под панелью меню расположена панель инструментов программы (рис. 6)

Рисунок 6 — Основное диалоговое окно программы

Чтобы продолжить работу с программой пользователю необходимо выбрать пункт меню «Файл» и щелкнуть на него левой кнопкой мыши. Далее появится выпадающий список, содержащий пункты «Создать», «Выход» (рис. 7).

Рисунок 7 — Меню «Файл» программы

Далее необходимо выбрать пункт меню «Создать» .

Рисунок 8 — Активное диалоговое окно программы

В поле программы появится пустая рабочая область с именем «Без имени». На нее следует помещать вершины, дуги ребра графа, их также можно удалять, измять им вес, выбрав соответствующие инструменты на панели инструментов. Чтобы найти кратчайший путь следует выбрать инструмент «поиск кратчайшего пути», поставить указтель мыши на исходную вершину и перетащить его до конечной. Пример нахождения пути показан на рисунке 9.

Рисунок 9 — Поиск кратчайшего пути

Заметим, что стрелка соединяющая, нужные нам вершины окрашивается в нужный цвет. После этого мы отпускаем левую клавишу мыши и видим следующие диалоговое окно:

Рисунок 10 — Завершенный поиск пути.

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

3.4 Контрольный пример

Допустим, имеется некоторый граф G (рисунок 11).

Рисунок 11

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

Построим матрицы D и P для начального состояния графа.

Рисунок 12 — Начальное состояние

Шаг 2.

Рис. 13. Матрицы D и P

Шаг 3.

Рис. 14. Матрицы D и P

Шаг 3

Рисунок 15 — Матрицы D и P

Шаг 4

Рисунок 16 — Матрицы D и P

Конечные матрицы D4 и P4 содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя вершинами. Например, кратчайшее расстояние между вершинами 1 и 5 равно d = 12.

Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j) состоит из ребра (i, j) только в том случае, когда P = j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку S= 4 и S = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1->4->5. Но так как S не равно 4, узлы 1 и 4 в определенном пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем S = 2 и S = 4, поэтому маршрут 1->4 заменяем 1->2->4. Поскольку S = 2 и S = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого пути равна 12.

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

Заключение

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

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

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

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

Таким образом, поставленные цель и задачи курсовой работы выполнены успешно.

1. Мендельсон Э.

Введение

в математическую логику. — М.: Наука, 2006. — 319с.

2. Спирина М. С. Дискретная математика: учеб. — М.: Академия, 2009.

3. Конспект лекций.