Список вариантов тем находится в приложении

Для заданного взвешенного ориентированного графа G = (V, Е) с истоком s и весовой функцией w: Е —" R алгоритм Беллмана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует. Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес. В этом алгоритме используется ослабление, в результате которого величина d[v], представляющая собой оценку веса кратчайшего пути из истока s к каждой из вершин v є V, уменьшается до тех пор, пока она не станет равна фактическому весу кратчайшего пути из s в v. Значение TRUE возвращается алгоритмом тогда и только тогда, когда граф не содержит циклов с отрицательным весом, достижимых из истока. Описание алгоритма при помощи псевдокода

Листинг программы на языке С++ приведен в приложении А.

3.Для расчета использовался следующий файл исходных данных4 41 2 6 2 3 7 3 4 5 3 1 2Где первая строка это количество размер матрицы смежности, а остальные строки задаются для каждого ребра в формате№ вершины№ вершины

Вес ребра

Работу программы демонстрирует следующая экранная форма, представленная на рис.

12.Рис.

12. Результат расчета кратчайших путей по методу Беллмана-Форда4. Сравнительный анализ алгоритмов поиска кратчайших путей

Для нахождения кратчайших путей в графах разработано и реализовано на различных языках программирования много различных алгоритмов. К ним можно отнести алгоритмы: Дейкстры, Дейкстры, ФлойдаУоршелла, Форда-Беллмана, Джонсона. Рассмотрим все эти алгоритмы, с целью сравнения. Алгоритм Дейкстрыалгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. В процессе работы алгоритма поддерживаются три множества: -М0—вершины, расстояние до которых уже вычислено (но, возможно, не окончательно);

1—вершины, расстояние до которых вычисляется;

2—вершины, расстояние до которых еще не вычислялось. В простейшем случае, сложность алгоритма составляет O (n2+ m) Здесь n-количество вершин графа, m-количество ребер графа. Эффективность метода Дейкстры существенно зависит от того, как организован поиск во множестве М1 вершины с наименьшим текущим расстоянием. Алгоритм Йенапредназначен для нахождения нескольких путей минимальной суммарной длины во взвешенном графе с неотрицательными весамимежду двумя вершинами. Алгоритм Беллмана — Фордарешает задачу о нахождении кратчайших путей из одной вершины во все остальные для случая, когда веса ребер могут быть отрицательными. Кроме того алгоритм контролирует отсутствие циклов отрицательного веса, достижимых из исходной вершины. Если в графе нет циклов отрицательного веса, алгоритм находит кратчайшие пути из заданной вершины во все остальные, если же в графе есть циклы отрицательного веса, то, по крайней мере, для некоторых вершин кратчайшего пути не существует. Идея алгоритма, также как и алгоритма Дейкстры, основана на последовательной релаксации ребер, пока не будут найдены кратчайшие расстояния.

Время работы алгоритма Форда-Беллмана есть O (n*m), стоимость инициализации есть O (n), а стоимость проверки на цикл отрицательного веса —O (m). Алгоритм Джонсонапозволяет найти кратчайшие пути между любыми двумя вершинами графа за O (n2log (n)+n*m). Следовательно, для достаточно разреженных графов, он эффективнее альтернативныхалгоритмов возведения в квадрат матрицы весов и алгоритма ФлойдаУоршелла. Этот алгоритм основан на идее изменения весов ребер графа. Если для ребер найти такую функцию, которая изменяет их веса, обеспечивая их не отрицательность и оставляя кратчайшие пути такими же (то есть состоящими из тех же ребер).

Алгоритм Флойда -Уоршелла это динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Его оченьлегко реализовать на любом языке программирования. Сложность алгоритма O (n3), т. е. алгоритм имееткубическую сложность. Тем не менее, алгоритм определяет только кратчайшие расстояния между всеми парами вершин, но не сохраняет информации о кратчайших путях [10].

Из рассмотренных выше алгоритмов можно сразу исключить алгоритм Йена, так как он предназначен для поиска путей равных по длине кратчайшему. В данной задаче до точки может быть только один путь. Алгоритм Джонсона эффективен только для разреженных графов, а при построении сети дорог используется полный граф. Остальные алгоритмы рассмотрены в книге И. В. Романовского [3]. В ходе рассмотрения этих методов автором были сделаны такие выводы:-«…Эффективность метода Дейкстры

Существенно зависит от того, как организован поиск вершины с наименьшим текущим расстоянием…" -«…Несмотря на очень высокую эффективность метода ДейкстрыГрибова, в практических задачах с „географической“ системой расстояний еще более эффективен метод, принадлежащий Б. Ю. Левиту. В сравнении с методом Дейкстры метод Левита проигрывает на том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М1.» Эксперименты показывают, что для графов с «геометрическим» происхождением, т. е. для графов, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым". В данной задаче ребра имеют значительный вес и несильно различаются между собой по величине иразбиение вершин на группы по принципу Дейкстры -Грибова может оказаться неэффективным, так как в одну группу может попасть одновременно много вершин или даже все. Что же касается алгоритма Левита, то он не имеет ни каких преимуществ в данном случае с алгоритмом Дейкстры, так как исходный граф строится не на основе транспортной сети, дуг с отрицательным весом нет, вес ребер графа определяется не только на основе расстояний между вершинами. В результатеисследований былапостроенатаблица 1, позволяющаясравнитьрассматриваемыеметоды

Таблица 1Сравнениеалгоритмовпоискакратчайших путей

АлгоритмОбъект работы

ДействиеСложность

Доп. память

Полезн.Матрица

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

Взвешенный граф без рёбер отрицательного веса

Поиск кратчайшего расстояния от одной вершины до всех остальных O (N2)O (N2), O (MlogN)O (N)10Алгоритм Уоршала

Взвешенный граф

Поиск кратчайшего расстояния от одной вершины до всех остальных O (N3)O (MN)O (N)5Алгоритм Флойда

Взвешенный граф

Поиск кратчайшего расстояния между каждой парой вершин O (N3)O (N2)8 В итоге из всех перечисленных алгоритмов лучше всего использовать алгоритм Дейкстры. Заключение

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

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

Алгоритм Форда-Беллмана. Флойда-Уоршела. Алгоритм Дейкстры находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. Вычислительная сложность алгоритма составляет O (n2+ m).Алгоритм Беллмана — Форда решает задачу о нахождении кратчайших путей из одной вершины во все остальные для случая, когда веса ребер могут быть отрицательными. Вычислительная сложность алгоритма — O (n*m), Алгоритм Флойда — Уоршелла это динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Его очень легко реализовать на любом языке программирования. Сложность алгоритма O (n3).Реализация и анализ алгоритмов позволяет сделать следующие выводы:

Все алгоритмы используют матричное представление графа в виде матрицы смежности;

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

ГОСТ «Единая система программной документации» (ЕСПД): ГОСТ 19.701−90.Акимов О. Е. Дискретная математика. Логика, группы, графы. Лаборатория Базовых Знаний. 2001

Алгоритмы решения экстремальных задач. И. В. Романовский. Главная редакция физико-математической литературы изд-ва «Наука». М 1977

Асеев Г. Г., Абрамов О. М., Ситников Д. Э. «Дискретная математика». Учебное пособие. Ростов-на-Дону «Феникс», Харьков «Торсинг» 2003

Асельдеров З.М., Донец Г. А. Представление и восстановление графов; Киев: Будiвельник — Москва, 2011. — 826 c. Ахо А. Структуры данных и алгоритмы: учеб. пособ. / А. Ахо, Д. Э. Хопкрофт, Д. Ульман; пер. с англ. — М.: Издательский дом «Вильяме», 2000

Ахтамова С. С. Алгоритмы поиска данных // Современные наукоемкие технологии. — 2007. — № 3 — С. 11−14.Берж К.

" Теория графов и ее применения". Издательство иностранной литературы. Москва. 1962

Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 2001

Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер с англ. И. В. Романовского. — СПб.: Невский диалект; БХВ-Петербург, 2003 г. — 654 с. Донец Г. А., Шор Н. З. Алгебраический подход к проблеме раскраски плоских графов; Евразия Экс-пресс — Москва, 2012. ;

224 c. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.

Лекции по теории графов; Либроком — Москва, 2012. — 392 c. Зыков А. А. Оcновы теории графов.— М.: Наука, 1987.— 381с. Исследования по прикладной теории графов; Наука. Новосибирск — Москва, 2008. — 168c. Камерон П., ван

Линт Д. Теория графов. Теория кодирования и блок-схемы; Харвест, Астрель, Сова — Москва, 2011. ;

717 c. Колмогоров А. Н. А. Н.

Колмогоров. Избранные труды. В 6 томах. Том 3.

Теория информации и теория алгоритмов; Наука —, 2008. — 264 c. Кормен, Томас X., Лейзерсон, Чарльз И., Ривсст, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. :

Пер. с англ. — М.: Издательский дом «Вильяме», 2005. —

1296 с. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. — 432с. Кузнецов Н. А., Фетисов В. Н.

«Алгоритм Дейкстры с улучшенной робастностью для управления маршрутизацией в IP-сетях», Автоматика и телемеханика, № 2, 2008

Левитин А. В. Алгоритмы: введение в разработку и анализ. — М.: «Вильямс», 2006. — с.

349 — 353. Майника Э. Алгоритмы оптимизации на сетях и графах. Пер. с англ. — М.:Мир, 1981, 328 с. Макконнелл Дж. Основы современных алгоритмов.

Москва: Техносфера, 2004. — 368с. Малинин Л. И., Малинина Н. Л. Изоморфизм графов в теоремах и алгоритмах; Либроком — Москва, 2009.

— 256 c. Мальцев Ю. Н., Петров Е. П.

Введение

в дискретную математику. Элементы комбинаторики, теории графов и теории кодирования; Эгмонт Россия Лтд., БУКИ — Москва, 2012. — 214 c. Мейн М. Структуры данных и другие объекты в С++ / М. МеЙн, У Савитч; пер.

с англ. — М.: Издательский дом «Вильяме», 2002

Мелихов А.Н., Берштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств — М.:Наука, 1974, 304 с. Мелихов А. Н., Берштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств; Типография А. В. Васильева — Москва, 2013. — 812 c. Николаев В. И., Иванова И. В. Теория алгоритмов: Текст лекций. — СПб.: СЗТУ, 1995

Носов В. А. «Комбинаторика и теория графов». 1999

Оре О. Теория графов.—М.: Наука, 1980.—336 с. Свами М., Тхуласирамап К. Графы, сети и алгоритмы.— М.: Мир, 1984, — 454 с. Татт УТеория графов.—М.: Мир, 1988

Теория графов в задачах и упражнениях. Более 200 задач с подробными решениями; Либроком — Москва, 2013. — 416 c. Уилсон Р.

Введение

в теорию графов; ЭлКниги — Москва, 2010. — 998 c. Харари Ф. Теория графов; Либроком — Москва, 2009. — 302 c. Хусаинов Б. С. Структуры и алгоритмы обработки данных: примеры на языке Си: учеб. пособ. / Б. С. Хусаинов.

— М.: Финансы и статистика, 2004. Bellman R. O n a RoutingProblem // QuarterlyofAppliedMathematics. 1958. V ol 16, No.

1. C. 87−90, 1958. Shimbel A. StructuralParametersofCommunicationnetworks, 1953, v.15, № 4.