Поиск кратчайшего пути. Алгоритм Флойда-Уоршелла
Определения теории графов. Реализация алгоритмов обработки графов в виде машинных процедур. Определение путей в графах. Математическое моделирование графов. Реализация алгоритма Флойда-Уоршелла без вычислительной системы. Оценка сложности алгоритма.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 18.10.2024 |
| Размер файла | 1,0 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Таблица 9 - Схема выполнения программы
|
k |
i |
j |
замена |
0 |
9 |
2 |
||
|
1 |
1 |
1 |
1 |
0 |
4 |
|||
|
1 |
1 |
2 |
2 |
4 |
0 |
|||
|
1 |
1 |
3 |
матрица смежности |
|||||
|
1 |
2 |
1 |
||||||
|
1 |
2 |
2 |
||||||
|
1 |
2 |
3 |
3<4, D[2][3] < 3 |
0 |
9 |
2 |
||
|
1 |
3 |
1 |
1 |
0 |
3 |
|||
|
1 |
3 |
2 |
2 |
4 |
0 |
|||
|
1 |
3 |
3 |
||||||
|
2 |
1 |
1 |
||||||
|
2 |
1 |
2 |
||||||
|
2 |
1 |
3 |
||||||
|
2 |
2 |
1 |
||||||
|
2 |
2 |
2 |
||||||
|
2 |
2 |
3 |
||||||
|
2 |
3 |
1 |
||||||
|
2 |
3 |
3 |
||||||
|
3 |
1 |
1 |
||||||
|
3 |
1 |
2 |
6<9, D[1][2] < 6 |
0 |
6 |
2 |
||
|
3 |
1 |
3 |
1 |
0 |
3 |
|||
|
3 |
2 |
1 |
2 |
4 |
0 |
|||
|
3 |
2 |
2 |
||||||
|
3 |
2 |
3 |
||||||
|
3 |
3 |
1 |
||||||
|
3 |
3 |
2 |
||||||
|
3 |
3 |
3 |
2.5 Оценка сложности алгоритма
Время выполнения этой программы, имеет порядок O(|V|3), поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство «правильности» работы этого алгоритма выполняется с помощью математической индукции по k, показывая, что на k-й итерации вершина k включается в путь только тогда, когда новый путь короче старого.
Заключение
Одним из наиболее используемым на практике алгоритмов для поиска кратчайших путей между всеми парами вершин во взвешенных графах является алгоритм Флойда - Уоршелла. Блочная версия алгоритма служит основой для получения эффективных параллельных алгоритмов при реализации на многоядерных центральных процессорах, компьютерах с распределенной памятью, графических процессорах. Увеличение зернистости вычислений в блочных версиях алгоритмов приводит к более эффективному использованию кешей и более эффективной организации параллельных вычислений. В этой работе предложено обобщение блочного алгоритма Флойда - Уоршелла. Порядок выполнения блоков вычислений реорганизован таким образом, чтобы элементы массива, участвующие в коммуникационных операциях как чтения, так и записи, реже вытеснялись из памяти с быстрым доступом. Тогда при реализации алгоритма на графическом процессоре реже, по сравнению с исходным блочным алгоритмом, используется медленная глобальная память.
Список использованной литературы
теория графов алгоритм флойда-уоршелла
1. Васильев В. С. Алгоритм. Свойства алгоритма [Электронный ресурс] - режим доступа: https://pro-prof.com/archives/578.
2. Васильев В. С. Блок-схемы алгоритмов сортировки пузырьком, выбором и вставками [Электронный ресурс] - режим доступа: https://pro-prof.com/archives/1462.
3. Дольников В. Л., Якимова О. П. Основные алгоритмы на графах: текст лекций. Ярославль: ЯрГУ, 2011. - 80 с.
4. Иглин, С.П. Решение некоторых задач теории графов в MATLAB [Текст] / С.П. Иглин // Exponenta Pro. Математика в приложениях. - 2004. - №4(4). - C. 28-33.
5. Кирсанов М. Н. Графы в Maple. Задачи, алгоритмы, программы. -- М.: ФИЗМАТЛИТ, 2007. -- 168 с.
6. Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы: построение и анализ»
7. Кристофидес Н. Теория графов. -- М.: Мир, 1978.
8. Макконелл Дж. Анализ алгоритмов. Активный обучающий подход. -- 3-е дополненное издание. М: Техносфера, 2009. - 416с.
9. Оре О. Графы и их применение. М.: Мир, 1965.
10. Савотченко С.Е., Кузьмичева Т.Г. Методы решения математических задач в Maple: Учебноепособие - Белгород: Изд. Белаудит, 2001. - 116 с.
11. Скиена С. Алгоритмы. Руководство по разработке. 2-е изд.: Пер. с англ. -- СПб.: БХВ-Петербург. 2011. -- 720 с.: ил.
12. Харари Ф. «Теория графов». // М.: "Мир", 2007.
Размещено на Allbest.ru
Подобные документы
Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
реферат [131,8 K], добавлен 11.11.2008Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Общая характеристика графов с нестандартными достижимостями, их применение. Особенности задания, представления и разработки алгоритмов решения задач на таких графах. Описание нового класса динамических графов, программной реализации полученных алгоритмов.
реферат [220,4 K], добавлен 22.11.2010Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014
