Материал: Граф и его элементы
В результате, нами получена матрица длин кратчайших путей между каждой
парой вершин графа. Ниже представлена таблица путей. Каждый элемент Cij
таблицы, это путь из вершины i в вершину j:
Таблица 10- Таблица путей
|
i/j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
- |
d1-2=1-2 |
d1-3=1-2-3 |
d1-4=1-4 |
d1-5=1-2-3-8-5 |
d1-6=1-2-6 |
d1-7=1-2-3-8-7 |
d1-8=1-2-3-8 |
|
2 |
d2-1=2-1 |
- |
d2-3=2-3 |
d2-4=2-1-4 |
d2-5=2-3-8-5 |
d2-6=2-6 |
d2-7=2-3-8-7 |
d2-8=2-3-8 |
|
3 |
d3-1=3-2-1 |
d3-2=3-2 |
- |
d3-4=3-2-1-4 |
d3-5=3-8-5 |
d3-6=3-6 |
d3-7=3-8-7 |
d3-8=3-8 |
|
4 |
d4-1=4-1 |
d4-2=4-1-2 |
d4-3=4-1-2-3 |
- |
d4-5=4-5 |
d4-6=4-1-2-6 |
d4-7=4-7 |
d4-8=4-1-2-3-8 |
|
5 |
d5-1=5-8-3-2-1 |
d5-2=5-8-3-2 |
d5-3=5-8-3 |
d5-4=5-4 |
- |
d5-6=5-8-3-6 |
d5-7=5-7 |
d5-8=5-8 |
|
6 |
d6-1=6-2-1 |
d6-2=6-2 |
d6-3=6-3 |
d6-4=6-2-1-4 |
d6-5=6-3-8-5 |
- |
d6-7=6-3-8-7 |
d6-8=6-3-8 |
|
7 |
d7-1=7-8-3-2-1 |
d7-2=7-8-3-2 |
d7-3=7-8-3 |
d7-4=7-4 |
d7-5=7-5 |
d7-6=7-8-3-6 |
- |
d7-8=7-8 |
|
8 |
d8-1=8-3-2-1 |
d8-2=8-3-2 |
d8-3=8-3 |
d8-4=8-3-2-1-4 |
d8-5=8-5 |
d8-6=8-3-6 |
d8-7=8-7 |
- |
В результате следуя из таблицы 10 и таблицы 9, кратчайший путь из вершины 1 в вершину 8, проходчит через вершины 1-2-3-8 и имеет вес равный 3.
. Создание приложения для решения задачи
7.1 Описание алгоритма
Ниже приведен алгоритм (рисунок 3) работы программы в упрощенном виде,
для лучшего восприятия хода работы программы.
Рисунок 12 - Алгоритм работы программы
7.2 Разработка программы
Для программной реализации алгоритма Флойда был использован язык программирования Delphi 7. Для оформления формы были использованы такие компоненты как: button (кнопка возврата условия, а так же для нахождения пути), StringGrid (отвечает за количество вершин), edit (для установки из какой в какую вершину будем искать кратчайший путь ), label (комментарий), LabelPath (вывод ответа), mainmenu (выпадающее меню).
В программном коде, было использовано всего две функции для обращения к алгоритму Флойда и восстанавливленния самого кратчайшего пути между любыми двумя заданными вершинами.
Остальной код программы состоит из процедур, отвечающих за функции такие как:
- чтение матрицы из Edit - procedure TForm1.InputMatrix;
- нахождение перспективной пары из множества конкурирующих пар - procedure TForm1.Konkurir;
- привидение (вычитание минимума элементов) матрицы, нахождение нижней оценки (границы) - procedure TForm1.Etap;
- вычеркивание из матрицы строки и столбца, определение новой диагонали - procedure TForm1.DelStrStolb;
- нахождение оптимального пути - procedure TForm1.OpredilPuti;
- проверка на замкнутость пути - procedure ProverkaIskl;
- процедура, описывающая нажатие на кнопку "найти" - procedure TForm3.Button2Click;
- увеличение/уменьшение количествава вершин указанных в Edit1 - procedure TForm3.Button1Click;
- несколько простейших процедур, описывающих выпадающее меню.
В практически всех процедурах используются циклы с параметрами, для перебора всех имеющихся строк и столбцов.
7.3 Тестирование программы
Введем исходные данные в матрицу StrinGrid (рисунок 13).
Рисунок 13 - Ввод исходных данных
Вводим значения в edit’ы,
от какой и до какой вершины желаем найти кратчайший путь (рисунок 14).
Рисунок 14 - Ввод вершин
Нажимаем кнопку «Найти» и смотрим результат (рисунок 15).
Рисунок 15 - Результат работы
Длина пути, найденное программным способом, совпадает с аналитическим. Можно сделать вывод, что и программное и аналитическое решение является верным.
7.4 Руководство пользователя
Запустив приложение Floid.exe, откроется окно позволяющее решать задачи методом алгоритма Флойда-Уоршелла
Все что вам требуется - это:
- ввести количество вершин;
- ввести вершины между которыми желаем найти кратчайший путь;
- нажать кнопку Найти;
- посмотреть результат работы программы.
При необходимости можно очистить форму при помощи кнопки «Очистить».
В представленной программе можно ввести данные задачи двумя способами:
вручную, либо программно, нажав на кнопку «Задача».
Заключение
Теория графов находит широкое применение в различных областях науки и техники, будь то физика, химия, математика и пр.
В процессе выполнения данной курсовой работы, цель была достигнута, поставленные задачи выполнены.
В начале курсовой работы была рассмотрена теория графов в общем, изучены понятия путей и маршрутов, постановку задач коммивояжера, понятие транспортной сети и алгоритм Флойда-Уоршелла. Данная мне тема «Задачи на графах» может найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины - роутеры, а ребра это связи между роутерами. Таким образом, чем короче будет путь, тем быстрее пакет достигнет пункта назначения и меньше будут информационные потери.
В данной курсовой работе реализованы поставленные задачи с помощью языка
программирования Delphi, был
разработан программный продукт «Алгоритм Флойда» для нахождения кратчайших
путей графа между его вершинами. Преимуществом данной программы является то,
что в ней реализованы принципы динамического программирования, то есть,
пользователь сам определяет количество вершин графа, количество ребер (дуг) и
их вес. В программе использован алгоритм Флойда-Уоршелла, который помогает
последовательно вычислить все значения длин кратчайших путей между вершинами.
Список использованных источников
1 Бурков, В.Н., Заложнев, А.Ю., Новиков, Д.А. Теория графов в управлении организационными системами. - Москва: Синтег, 2001.
Новиков, Ф.А. Дискретная математика для программистов. - Санкт-Петербург: Питер, 2002.
Новиков, Ф.А. Дискретная математика: Учебник для вузов. Стандарт третьего поколения. Санкт-Петербург: Питер, 2011.
Прилуцкий, М.Х. Математические основы информатики. - Нижний Новгород, 2000.
Партыка, Т.Л., Попов, И.И. Математические методы- Москва, 2005.