Введение 3

1. Раздел 1. Общая часть 4

1.1. Постановка задачи 4

В среде Borland Delphi 7 необходимо разработать приложение, которое реализует метод Флойда. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Постановка задачи: пусть дан непустой взвешенный граф G=(V, E) с произвольными весами ребер (дуг). Требуется найти длины кратчайших путей между всеми парами вершин графа

Прикладная задача, которую будет решать алгоритм Флойда, заключается в следующем: Телефонная компания обслуживает семь удаленных друг от друга районов, которые связаны сетью. Компании необходимо определить наиболее эффективные маршруты пересылки сообщений между любыми двумя районами.

1.2. Цели разработки 5

1.3. Построение математической модели 6

1.4. Описание математических формул 9

2. Раздел 2: Специальная часть 10

2.1. Расчет математической модели 10

2.2. Описание программы 16

2.2.1.О программе 17

2.2.2.Алгоритм работы программы 18

2.2.3.Входные данные 21

2.2.4.Выходные данные 21

2.4.Тестирование программы 25

2.5.Руководство пользователю 28

Заключение 29

Литература 30

Приложение А

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

Наиболее распространенные методы поиска кратчайших расстояний – это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k – кратчайших путей в графе).

Целью курсовой работы было изучить и реализовать на практике алгоритм Флойда для нахождения кратчайших путей в графе. Объектом работы является алгоритм Флойда.

Задачи работы:

1. Изучение теории графов.

2. Изучение алгоритма Флойда для нахождения кратчайших путей в графе.

3. Создание приложения, которое реализует алгоритм Флойда.

4. Отладка приложения.

1. Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации. М. Иза-во МГТУ им. Н.Э.Баумана, 2003. – 325 с.

2. Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 2002. – 165 с.

3. Гофман В.Э., Хомоненко А.Д. Delphi 5. – СПб.:БХВ – Санкт Петербург, 2002. – 800с.

4. Королев Н.А. Введение в Delphi 7. М. ЮНИТИ, 2005. – 322 с.

5. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 2002. – 222с.

6. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 2000. – 302 с.

7. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992. – 332 с.

8. Оре О. Теория графов. – М.: Наука, 1980. – 345 с.

Примечаний нет.