Задача кратчайшего пути

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

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Национальный исследовательский технологический университет «МИСиС»

Институт ИТАСУ Кафедра инженерной кибернетики

Специальность 231300 «Прикладная математика»

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

по дисциплине «Алгоритмы дискретной математики»

на тему: «Задача кратчайшего пути»

Студенты Корень Маргарита Романовна

Крутов Олег Денисович

Додонова Анна Алексеевна

Группа ММ-14-2

Руководитель работы Пышняк М.О.

Оценка Корень Маргарита Романовна

Крутов Олег Денисович

Додонова Анна Алексеевна

Москва 2016

Министерство образования и науки Российской Федерации

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

Институт ИТАСУ Кафедра инженерной кибернетики

Специальность 231300 «Прикладная математика»

Задание на курсовую работу по дисциплине «Алгоритмы дискретной математики»

Студент Корень Маргарита Романовна

Группа ММ-14-2

Тема - «Задача кратчайшего пути».

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

Перечень подлежащих разработке вопросов

1. Исходные данные: монохромное изображение буквы или иероглифа.

2. Сроки начала и окончания работы: 15.02.16 - 07.06.16

3. Задание выдано: 15.02.16

4. Руководитель работы: Пышняк М.О.

5. Задание принял к исполнению студент:

Корень Маргарита Романовна



Министерство образования и науки Российской Федерации

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

Институт ИТАСУ Кафедра инженерной кибернетики

Специальность 231300 «Прикладная математика»

Задание на курсовую работу по дисциплине «Алгоритмы дискретной математики»

Студент Крутов Олег Денисович

Группа ММ-14-2

1. Тема - «Задача кратчайшего пути».

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

Перечень подлежащих разработке вопросов.

1. Исходные данные: монохромное изображение буквы или иероглифа.

2. Сроки начала и окончания работы: 15.02.16 - 07.06.16

3. Задание выдано: 15.02.16

4. Руководитель работы: Пышняк М.О.

5. Задание принял к исполнению студент:

Крутов Олег Денисович



Министерство образования и науки Российской Федерации

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

Институт ИТАСУ Кафедра инженерной кибернетики

Специальность 231300 «Прикладная математика»

Задание на курсовую работу по дисциплине «Алгоритмы дискретной математики»

Студент Додонова Анна Алексеевна

Группа ММ-14-2

1. Тема - « Задача кратчайшего пути «.

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

Перечень подлежащих разработке вопросов.

1. Исходные данные: монохромное изображение буквы или иероглифа.

2. Сроки начала и окончания работы: 15.02.16 - 07.06.16

3. Задание выдано: 15.02.16

4. Руководитель работы: Пышняк М.О.

5. Задание принял к исполнению студент:

Додонова Анна Алексеевна



Оглавление

Введение

1. Аналитический обзор литературы

1.1 История возникновения

1.2 Основные понятия

1.3 Алгоритмы решения задачи

1.4 Актуальность и применение

2. Основная часть

2.1 Содержательная постановка задачи

2.2 Математическая постановка задачи

2.2.1 Формулировка в терминах теории графов

2.2.2 Сведение к задаче целочисленного линейного программирования (ЦЛП)

2.2.3 Формулировка ЗКП в терминах динамического программирования (ДП)

2.3 Решение поставленной задачи

2.3.1 Алгоритм работы программы

2.4 Программная реализация

Вывод по работе

Список литературы

Приложение



Введение

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

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

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

1. Аналитический обзор литературы

1.1 История возникновения

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

История возникновения теории графов берет своё начало с задачи о Кёнигсбергских мостах - старинной математической задачи, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Даная задача впервые была решена русско-немецким математиком Леонардом Эйлером в 1936 году. В своем письме к итальянскому математику и инженеру Маринони от 13 марта 1736 года он формулирует основные выводы теории графов, что и послужило началом данной математической дисциплине.

Однако эта статья Эллера была единственной почти в течение ста лет. Интерес к развитию теории графов возродился на рубеже XIX-XX столетий. Имелось множество причин для подобного оживления изучения графов. Естественные науки оказали своё влияние на это благодаря исследованию электрических сетей и молекулярных схем. Также толчок к развитию теория графов получила, когда резко возросло число работ в области топологии и комбинаторики.

1.2 Основные понятия

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

где G - граф с множеством вершин V и некоторым семейством сочетаний (пар) вида

указывающее, какие вершины считаются соединенными. В соответствии геометрическим представлением графа каждая конкретная пара называется ребром графа, вершины a_i и a_i+1 которого называются концами ребра E. Вершины а_i и a_i+1 инцидентны Е, а также ребро Е инцидентно вершинам а_i и a_i+1. Две вершины (или два ребра) инцидентными быть не могут.

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

Граф называется помеченным (или перенумерованным), если его вершины отличаются друг от друга какими-либо пометками. (тоже оре)

Рис. 1 - пример перенумерованных графов: ориентированного и неориентированного



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

Взвешенным называется граф, каждому ребру которого присвоено значение (вес ребра). Обычно вес -- вещественное число, в таком случае его можно интерпретировать как «длину» ребра. [2]

Путь (маршрут) на графе определяется последовательностью вершин и ребер

a₁E₁a₂E₂a₃…a_iE_ia_i+1,

где a_i - вершины,

E_i = (a_i, a_i+1) - ребро.

Для ориентированного графа существует два типа маршрутов: неориентированный и ориентированный. Неориентированным маршрутом называется последовательность вершин a_1, a₂... a_i такая, что для каждого i = 1, 2…n-1 хотя бы одно из ребер (a_i, a_i+1), (a_i+1, a_i) принадлежит графу. Маршрут называется ориентированным, если для каждого i пара (a_i, a_i+1) является ребром графа. Таким образом, при движении по неориентированному маршруту в ориентированном графе ребра могут проходиться как в направлении ориентации, так и в обратном, а при движении вдоль ориентированного маршрута - только по направлению ориентации ребра.

Соответственно двум типам маршрутов определяются и два типа связности ориентированных графов. Орграф называется связным (или слабо связным), если для каждой пары вершин в нем имеется соединяющий их маршрут; он называется сильно связным, если для каждой упорядоченной пары вершин (a_i, a_i+1) в нем имеется ориентированный маршрут, ведущий из a_i в a_i+1.

Сформулированные выше определения для графа достаточны для многих задач, в том числе и для задачи кратчайшего пути, которой посвящена данная работа. [3]

Задача кратчайшего пути является одной из наиболее фундаментальных задач теории графов. Суть задачи заключается в нахождении кратчайшего пути между двумя вершинами на графе. Кратчайший путь подразумевает минимальную сумму весов ребер, составляющих маршрут между необходимыми вершинами. Интерес к этой задаче обуславливается тем, что она применима во многих областях нашей повседневной жизни. Один из множества примеров того, как используется задача кратчайшего пути - это нахождение оптимального маршрута в картографических сервисах, таких как Google.Maps и Яндекс.Карты, которыми практически каждый из нас пользуется ежедневно. Дорожную карту можно представить в виде взвешенного ориентированного графа, вершинами которого будут являться города, а дороги, соединяющие их - ребрами. Тогда весом ребра будет являться расстояние между двумя городами (или иной выборочный параметр, такой как время в пути и т.п.). Используя подобное представление, поиск самого удачного маршрута будет реализоваться с помощью наиболее эффективных алгоритмов поиска кратчайшего пути между вершинами на графе. В общем случае задачу кратчайшего пути можно сформулировать следующим образом: дан взвешенный ориентированный граф с весовой функцией , отображающей ребра на их веса, значения которых выражаются действительными числами. Нам необходимо найти минимальное значение веса пути между нужными нам вершинами, который равен суммарному весу входящих в него отдельных ребер:

). [4]



1.3 Алгоритмы решения задачи

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

· Алгоритм Дейкстры (находит кратчайший путь от одной из вершин графа до всех остальных; алгоритм работает только для графов без рёбер отрицательного веса)

· Алгоритм Белмана-Форда (находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе; вес ребер может быть отрицательным)

· Алгоритм Флойда-Уоршелла (находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа)

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

Алгоритм Дейкстры по праву считается одним из наиболее эффективных алгоритмов решения задачи отыскания кратчайшего пути в графе для случая неотрицательных весов дуг. Он был разработан нидерландским математиком Эдсгером Дейстрой в 1959 году. Данный алгоритм широко применяется в программировании, а также в протоколах маршрутизации (таких как OSPF и IS-IS).

Суть алгоритма заключается в следующем: сопоставим каждой вершине метку - минимальное известное расстояние от данной вершины до a. Алгоритм работает пошагово, на каждом последующем шаге посещая одну из вершин, пытаясь уменьшить величину метки. Работа алгоритма завершится, когда все вершины буду посещены. Первая метка, с которой начинается алгоритм, полагается равной 0, а метки остальных вершин - бесконечности (метка бесконечности означает, что расстояние то данной вершины пока неизвестно). До того момента, когда все вершины окажутся посещенными, будет выбираться некоторая из ещё не посещённых вершин, имеющая минимальную метку. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Вершины, в которые ведут рёбра из u, назовём соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещённую и повторим шаг алгоритма.

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

Алгоритм Белмана-Форда.

Данный метод медленнее, чем алгоритм Дейкстры для той же задачи, но более универсален, так как он способен обрабатывать графы, в которых некоторые из весов имеют отрицательные значения. Алгоритм назван в честь Ричарда Беллмана и Лестера Форда-младшего, которые опубликовали его в 1958 и 1956 годах, соответственно, работая независимо друг от друга. Эдвард Ф. Мур также опубликовал тот же алгоритм в 1957 году, и по этой причине его также иногда называют «Алгоритм Беллмана-Форда-Мура».

Алгоритм Флойда-Уоршелла

Пусть вершины графа

пронумерованы от 1 до и введено обозначение



(i<j<k)

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

Существует два варианта значения

:

1. Кратчайший путь между не проходит через вершину , тогда

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

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

Тогда рекуррентная формула для имеет вид:

-- длина ребра



Алгоритм Флойда-Уоршелла последовательно вычисляет все значения для от 1 до . Полученные значения являются длинами кратчайших путей между вершинами

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

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

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

1. Разбиение задачи на подзадачи меньшего размера.

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

3. Использование полученного решения подзадач для конструирования решения исходной задачи.

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

1.4 Актуальность и применение

Алгоритм Дейкстры, а также его модификации используются в области сетей, транспортных потоков, и, конечно же, в области обработки графов. Например, протокол динамической маршрутизации OSPF разбивает процесс построения таблицы маршрутизации на два этапа, и второй этап состоит в нахождении оптимальных маршрутов с помощью созданного на первом этапе графа. На этом этапе применяется итеративный алгоритм Дейкстры: каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети. В каждом найденном таким образом маршруте запоминается только один шаг - до следующего маршрутизатора. Данные об этом шаге попадают в таблицу маршрутизации. Если несколько маршрутов имеют одинаковую метрику до сети назначения, то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов. Также алгоритм применяется при эвакуации населения из очагов бедствия. Оптимальные маршруты до пунктов сбора транспорта для каждой группы людей в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.

В области разработки игр широкое применение находит алгоритм А*, классическим примером его применения является игра «Lines», «ColorLines», в которой игроку необходимо составить в ряд несколько шаров, путь шара как раз рассчитывается с помощью этого алгоритма. Кроме этого А* применяется во многих играх жанра RTS (Real Time Strategy), его модификации применяются в таких крупных проектах как «StarCraft2» и «Warcraft3».

алгоритм задача граф программный



2. Основная часть

2.1 Содержательная постановка задачи

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

2.2 Математическая постановка задачи

2.2.1 Формулировка в терминах теории графов

Определение:

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

.

Каждой дуге с номером, где

(разность номеров вершин)

припишем ее длину

.

Путем (маршрутом) назовем в графе конечную последовательность вершин и дуг (ребер)



;

длина пути из вершины в .

Рис.1.

На рис 1. удалены петли и параллельные дуги большой длины. Для любого пути от до имеем

например, для последовательности вершин (0,2,5,6) имеем (2-0) + (5-2) + (6-5) = 6 = . В таблице 1 приведены длины всех дуг для . Требуется найти кратчайший путь из вершины в вершину .

Табл. 1.

	3	5	4	3	3	5	4
	4	5	3	5	3	5	3	4

2.2.2 Сведение к задаче целочисленного линейного программирования (ЦЛП)

Пусть и если дуга включена или не включена в маршрут . Тогда

если

Задача ЗКП, сформулированная в терминах теории графов, может быть решена алгоритмами Флойда, Дейкстры и т.д. Для задачи, сведенной к ЦЛП, естественно применять известные способы решения подобных задач - методы отсечения (Гомори), ветвей и границ и т.д.

2.2.3 Формулировка ЗКП в терминах динамического программирования (ДП)

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

Итак, рис. 1 (с учетом таблицы 1) представим в виде



Рис.2.

Номера вершин внутри кружков, около каждой дуги указана ее длина. Концы дуг, идущих из отнесем к стадии I. Концы дуг, идущих в отнесем к стадии III. Тогда дуги (1,2), (1,3) (2,3) на стадии I можно удалить, ибо, например,

по правилу треугольника. Таким образом, представление в соответствии с рисунком 2 возможно только при выполнении этого правила. Аналогично на стадии II удаляем дуги (3,4), (3,5) (4,5). Для того, чтобы любой путь от 0 до содержал одинаковое число вершин, некоторые из них можно повторять на разных стадиях, например, вершину (3). Тогда длина дуги (3,3) равна нулю.

Обозначим множество вершин, находящихся на стадии т.е.

В каждую из вершин входит, по крайней мере, одна дуга из множества вершин на стадии при этом

и .

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

Итак, на всех стадиях в качестве параметров состояния будем выбирать вершины на предыдущей стадии, то есть

,

причем количество состояний равно. Пусть - длина кратчайшего маршрута от вершины до вершины. Из вершины идут дуги в вершины.

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

Здесь в соответствии с принципом ДП процесс оптимизации разбит на N стадий, причем решение ведется, начиная со стадии до стадии 1. Перебирая в процедуре минимизации индексы , мы тем самым рассматриваем различные вершины на стадии, то есть разные функции.

Итак, решим задачу (*) для рисунка 2.

III стадия: (дуга (4,6)); (дуга (5,6)); (дуга (3,6));

II стадия:

;

(дуга (2,5));

Аналогично находим (дуга (3,3));

I стадия:

(дуга (0,3)).

Итак, оптимальная траектория от вершины 0 до 6 есть (0,3,6). Таким образом, после разбиения множества вершин по стадиям решение ЗКП приводится с помощью процедуры (*). Если для всех дуг выполняется правило треугольника, разбиение вершин по стадиям труда не представляет и может быть проведено по единой схеме с помощью компьютера. На соседних стадиях располагаются вершины, соединенные хотя бы одной дугой, причем одну и ту же вершину в случае необходимости можно поместить на соседних стадиях, соединив их дугой нулевой длины. Этот прием используется для того, чтобы поместить конечную точку маршрута на последнюю стадию (смотри рисунок 3).

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

Пусть для графа на рис 1. длина дуги (0,2) равна 7, все прочие длины сохраняются. Требуется разбить множество по стадиям. Так как

(3+3<7), дуга (0,2)

размыкается и на стадии I остаются только вершины 1 и 3. На стадии II к вершинам 4 и 5 добавляются вершины 2 и 6.

Для всех дуг, идущих из вершин 1 и 3 в вершины 2,4,5,6 правило треугольника выполняется. Вершину 6 в этом случае можно заменить вершиной 3, а дугу (3,3) положить равной 0. Граф на рисунке 1 примет вид:

Рис. 3.

Решение задачи (*) для рисунка 3 будет таким же как и для рисунка 2.

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



2.3 Решение поставленной задачи

2.3.1 Алгоритм работы программы

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

Таким образом, программа находить кратчайший путь от начальной до конечной точки заданного маршрута.

Пример итога работы программы:

2.4 Программная реализация

Для реализации нашего алгоритма мы использовали язык программирования java. Системные требования проекта соответствуют системным требованиям java-машины. Для компиляции требуется IDEA или только java-машина для запуска jar-файла. Листинг кода находится в Приложении.



Вывод по работе

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



Список литературы

1. Оре О. Теория графов. - 2-к изд.- М: Наука. Главная редакция физико-математической литературы, 1980, 336с.

2. Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие /Б. Н. Иванов. - М.: Лаборатория Базовых Знаний, 2003. - 288с.:ил.

3. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: Учебник. - Нижний Новгород: Изд-во ННГУ, 2005. 307 с.

4. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М.: «Вильямс», 2006. -- С. 1296. -- ISBN 0-07-013151-1.



Приложение

package pack;

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Scanner;

/**

* Created by akella on 29.05.2016.

*/

public class Matrix {

public int length;

public int start,finish;

public double[][] matrix;

public Matrix(){}

public void Reader()

{

try {

Scanner sc = new Scanner(new File(«input.txt»));

start=sc.nextInt();

finish=sc.nextInt();

length=sc.nextInt();

matrix=new double[length][length];

while (sc.hasNext()) {

int a = sc.nextInt();

int b = sc.nextInt();

int c = sc.nextInt();

matrix[a][b] = c;

}

sc.close();

} catch (FileNotFoundException e) {

e.printStackTrace();

}

}

public void write() {

for (int i = 0; i < length; i++) {

for (int j = 0; j < length; j++) {

System.out.print(matrix[i][j]);

System.out.print(« «);

}

System.out.println();

}}}

import pack.Matrix;

public class Main {

public static void func(Matrix temp, double[] arr, int[] path, int start) {

int a = temp.length;

for (int j = 0; j < a; j++) {

if (temp.matrix[start][j] != 0) {

if (arr[j] > temp.matrix[start][j] + arr[start]) {

arr[j] = temp.matrix[start][j] + arr[start];

path[j] = start;

}

temp.matrix[start][j] = 0;

func(temp, arr, path, j);}}} ;

public static void main(String[] args) {

long startTime = System.currentTimeMillis();

Matrix temp = new Matrix();

temp.Reader();

double sum=0;

double[] arr = new double[temp.length];

int[] path = new int[temp.length];

for (int i = 0; i < temp.length; i++)

arr[i] = Double.POSITIVE_INFINITY;

arr[temp.start] = 0;

func(temp, arr, path, temp.start);

temp.Reader();

System.out.print(«Стартовая вершина:» + temp.start + « «);

System.out.println(«Конечная вершина:» + temp.finish + « «);

System.out.print(«Путь: «);

String str = temp.finish + «>-»;

int k = temp.finish;

if (arr[temp.finish] != Double.POSITIVE_INFINITY) {

while (k != 0) {

str = str + path[k] + «>-»;

sum+=temp.matrix[path[k]][k];

k = path[k]; }

str = str.substring(0, str.length() - 3);

str = new StringBuilder(str).reverse().toString();

if (temp.start == 0)

str = 0 + str;

System.out.println(str);

System.out.println(«Длина маршрута=« +sum);

} else

System.out.println(«Данный маршрут проложить невозможно»);

long endTime = System.currentTimeMillis();

long totalTime = endTime - startTime;

System.out.println(«time=«+totalTime+»ms»);

}

}

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