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;
- несколько простейших процедур, описывающих выпадающее меню.
В практически всех процедурах используются циклы с параметрами, для перебора всех имеющихся строк и столбцов.
- Введение
- 1. Граф и его элементы
- 1.1 Основные понятия
- 1.2 Ориентированный граф
- 1.3 Неориентированный граф
- 1.4 Смежность
- 1.5 Маршруты и пути
- 2. Постановка задачи коммивояжера и алгоритмы решения
- 2.1 Задача коммивояжера
- 2.2 Методы решения задачи коммивояжера
- 3. Понятия транспортной сети
- 3.1 Понятие увеличивающая дуга, цепь, разрез
- 4. Алгоритм Флойда-Уоршелл
- 5. Постановка задачи
- 6. Решение задачи аналитическим методом
- 7. Создание приложения для решения задачи
- 7.1 Описание алгоритма
- 7.3 Тестирование программы
- 7.4 Руководство пользователя
- Заключение
- Элементы теории графов
- Элементы теории графов
- Элементы графа
- Элементы теории графов. Оптимизация на графах.
- § 2.2. Отношения и характеристики элементов графа
- 15 Элементы теории графов. Способы задания графов.
- Элементы теории графов.
- Элементы теории графов
- Элементы теории графов
- 1. Графы и их элементы.