Поиск кратчайшего пути. Алгоритм Флойда-Уоршелла
Определения теории графов. Реализация алгоритмов обработки графов в виде машинных процедур. Определение путей в графах. Математическое моделирование графов. Реализация алгоритма Флойда-Уоршелла без вычислительной системы. Оценка сложности алгоритма.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 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Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
реферат [106,0 K], добавлен 27.11.2008Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
курсовая работа [1,0 M], добавлен 26.09.2013Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Основополагающие понятия теории графов. Определение эквивалентности, порождаемое группой подстановок, и доказательство леммы Бернсайда о числе ее классов. Понятие перечня конфигурации и доказательство теоремы Пойа. Решение задачи о перечислении графов.
курсовая работа [649,2 K], добавлен 18.01.2014
