Содержание
Введение3
1.Теоретическая часть4
1.1.Графы. Представление графов в памяти компьютера4
1.2.Поиск кратчайших путей из фиксированной вершины до всех остальных6
1.3.Поиск кратчайшего пути между каждой парой вершин7
2.Практическая часть11
2.1.Текст программы11
2.2.Описание работы программы16
Заключение18
Список литературы19
Выдержка из текста
Заключение
В процессе выполнения данной курсовой работы был решен ряд задач.
Во-первых, были рассмотрены основные понятия теории графов (1 часть теоретического раздела). Во-вторых, были изучены алгоритмы поиска кратчайшего пути между определенной вершиной графа и остальными вершинами алгоритм Беллмана-Форда и алгоритм Дейкстры (2 часть теоретического раздела). В-третьих, был подробно рассмотрен алгоритм Флойда-Уоршалла поиска кратчайших путей между каждой парой вершин (3 часть теоретического раздела).
Затем в соответствии с алгоритмом Флойда-Уоршалла в среде Delphi было разработано приложение, находящее кратчайшие пути между каждой парой вершин по заданной пользователем матрице весов (в данном приложении веса целые числа, как положительные, так и отрицательные. Единственное ограничение, накладываемое алгоритмом отсутствие отрицательных циклов в графе). После разработки программный продукт был протестирован на нескольких графах с различным числом вершин. Ошибок найдено не было.
Список использованной литературы
1.Алгоритм Флойда // [Электронный ресурс]: портал Факультета «Компьютерные информационные технологии» Национального технического университета Украины ХПИ. Электрон. дан. Режим доступа: http://khpi iip.mipk.kharkiv.edu/library/datastr/book_sod/kgsu/din_0124.html . Загл. с экрана.
2.Алгоритм Флойда-Уоршелла // [Электронный ресурс]: Энциклопедия Википедия. Электрон. дан. Режим доступа: http://ru.wikipedia.org/wiki/Алгоритм_Флойда__Уоршелла. Загл. с экрана.
3.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Бином, 2000. 960с.
4.Красиков И.В., Красикова И.Е. Алгоритмы просто как дважды два. М.: Эксмо, 2007. 256с.
5.Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2004. 368с.
С этим материалом также изучают
... –1 – это контур. Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает ...
... поиска кратчайшего пути между определенной вершиной графа и остальными вершинами алгоритм Беллмана-Форда и алгоритм Дейкстры (2 часть теоретического раздела). В-третьих, был подробно рассмотрен алгоритм Флойда-Уоршалла поиска кратчайших путей между ...
... поиска кратчайшего пути между определенной вершиной графа и остальными вершинами алгоритм Беллмана-Форда и алгоритм Дейкстры (2 часть теоретического раздела). В-третьих, был подробно рассмотрен алгоритм Флойда-Уоршалла поиска кратчайших путей между ...
... FloydWarshall, выполняющая нахождение кратчайших путей между вершинами графа. После выполнения подпрограммы FloydWarshall в цикле для каждой пары вершин печатается заголовок, кратчайшее расстояние между вершинами (если путь существует), а затем ...
... Алгоритм Флойда для решения задачи поиска кратчайшего пути в графе 8 ГЛАВА 2. РАЗРАБОТКА ПАРАЛЛЕЛЬНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ПОИСКА КРАТЧАЙШЕГО ПУТИ МЕТОДОМ ФЛОЙДА 11 2.1 Последовательный алгоритм Флойда 11 2.2 Распараллеливание алгоритма Флойда ...
... 1.3 Задача поиска всех кратчайших путей 7 1.4 Последовательный алгоритм Флойда 8 1.5 Технология CUDA 9 ГЛАВА 2. РАЗРАБОТКА ПАРАЛЛЕЛЬНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФЕ 10 2.1 ...
... пути Pab из вершины a в вершину b, как сумму длин ребер, составляющих этот путь.Задача отыскания кратчайшего пути для заданных вершин s,tV заключается в построении пути ... изучить алгоритм Флойда для нахождения кротчайших путей в графе. Написать ...
... машину как граф, где вершины описывают состояния и ребра, описывают возможные переходы, алгоритмы кратчайшего пути могут быть ... В теории графов задача кратчайшего пути является задачей нахождения пути между двумя вершинами (или узлами) в графе, так что ...
... Данная курсовая работа решает такую актуальную задачу, как поиск кратчайшего пути. Сама задача является актуальной как для общественных ... БХВ-Петербург, 2008. - 464 с.: ил. 4) Федоренко Ю.П. Алгоритмы и программы на C++ Builder. - М.: ДМК Пресс, ...
