Материал: Граф и его элементы
Таблица 5 - Матрица D4
|
D4= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
14 |
3 |
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
15 |
2 |
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
16 |
1 |
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
16 |
3 |
|
7 |
14 |
15 |
16 |
5 |
4 |
16 |
0 |
8 |
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D5 (Таблица 6). включив в нее рассчитанные элементы из приложения.
Таблица 6 - Матрица D5
|
D5= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
|
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D6. (Таблица 7). включив в нее рассчитанные элементы из приложения.
Таблица 7 - Матрица D6
|
D6= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
|
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D7. (Таблица 8). включив в нее рассчитанные элементы из приложения.
Таблица 8 - Матрица D7
|
D7= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
0 |
1 |
2 |
9 |
9 |
2 |
13 |
3 |
|
2 |
1 |
0 |
1 |
10 |
10 |
1 |
14 |
2 |
|
3 |
2 |
1 |
0 |
11 |
11 |
2 |
15 |
1 |
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
5 |
9 |
10 |
11 |
9 |
0 |
11 |
4 |
4 |
|
6 |
2 |
1 |
2 |
11 |
11 |
0 |
15 |
3 |
|
7 |
13 |
14 |
15 |
5 |
4 |
15 |
0 |
8 |
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
Представим матрицу D8, включив в нее рассчитанные элементы.
Таблица 9 - Матрица D8
|
D8= |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
0 |
1 |
2 |
9 |
7 |
2 |
11 |
3 |
|
2 |
1 |
0 |
1 |
10 |
6 |
1 |
10 |
2 |
|
3 |
2 |
1 |
0 |
11 |
5 |
2 |
9 |
1 |
|
4 |
9 |
10 |
11 |
0 |
9 |
11 |
5 |
12 |
|
5 |
7 |
6 |
5 |
9 |
0 |
7 |
4 |
4 |
|
6 |
2 |
1 |
2 |
11 |
7 |
0 |
11 |
3 |
|
7 |
11 |
10 |
9 |
5 |
4 |
11 |
0 |
8 |
|
8 |
3 |
2 |
1 |
12 |
4 |
3 |
8 |
0 |
В результате, нами получена матрица длин кратчайших путей между каждой парой вершин графа. Ниже представлена таблица путей. Каждый элемент 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, откроется окно позволяющее решать задачи методом алгоритма Флойда-Уоршелла
Все что вам требуется - это:
- ввести количество вершин;
- ввести вершины между которыми желаем найти кратчайший путь;
- нажать кнопку Найти;
- посмотреть результат работы программы.
При необходимости можно очистить форму при помощи кнопки «Очистить».
В представленной программе можно ввести данные задачи двумя способами: вручную, либо программно, нажав на кнопку «Задача».