7 Создание приложения для решения задачи
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, был разработан программный продукт «Алгоритм Флойда» для нахождения кратчайших путей графа между его вершинами. Преимуществом данной программы является то, что в ней реализованы принципы динамического программирования, то есть, пользователь сам определяет количество вершин графа, количество ребер (дуг) и их вес. В программе использован алгоритм Флойда-Уоршелла, который помогает последовательно вычислить все значения длин кратчайших путей между вершинами.