Содержание
Введение3
1.Теоретическая часть4
1.1.Графы. Представление графов в памяти компьютера4
1.2.Поиск кратчайших путей из фиксированной вершины до всех остальных6
1.3.Поиск кратчайшего пути между каждой парой вершин7
2.Практическая часть11
2.1.Текст программы11
2.2.Описание работы программы15
Заключение17
Список литературы18
Выдержка из текста
void __fastcall TForm1::Button1Click(TObject *Sender);
Обработчик нажатия на кнопку Button1 («Найти кратчайшие пути»). При наступлении этого события компонент ListBox1 очищается, затем вызывается основная подпрограмма FloydWarshall, выполняющая нахождение кратчайших путей между вершинами графа. После выполнения подпрограммы FloydWarshall в цикле для каждой пары вершин печатается заголовок, кратчайшее расстояние между вершинами (если путь существует), а затем вызывается подпрограмма печати кратчайшего пути PrintPath.
Рассмотрим подробнее работу указанных подпрограмм.
Список использованной литературы
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 часть теоретического раздела). В-третьих, был подробно рассмотрен алгоритм Флойда-Уоршалла поиска кратчайших путей между ...
... вызывается подпрограмма печати кратчайшего пути PrintPath. Во-первых, были рассмотрены основные понятия теории графов (1 часть теоретического раздела). Во-вторых, были изучены алгоритмы поиска кратчайшего пути между определенной вершиной графа и ...
... поиска кратчайшего пути между определенной вершиной графа и остальными вершинами алгоритм Беллмана-Форда и алгоритм Дейкстры (2 часть теоретического раздела). В-третьих, был подробно рассмотрен алгоритм Флойда-Уоршалла поиска кратчайших путей между ...
... Алгоритм Флойда для решения задачи поиска кратчайшего пути в графе 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 заключается в построении пути ... изучить алгоритм Флойда для нахождения кротчайших путей в графе. Написать ...
... машину как граф, где вершины описывают состояния и ребра, описывают возможные переходы, алгоритмы кратчайшего пути могут быть ... В теории графов задача кратчайшего пути является задачей нахождения пути между двумя вершинами (или узлами) в графе, так что ...
... создать прикладную программу, реализующую алгоритм поиска в графе вершин, имеющих наибольшее окружение. Пусть дан граф и число k ... Граф3 1.1.Основные термины и понятия3 1.2. Расстояние между вершинами, ярусы и диаметр графа.4 1.3. Достижимость ...
