Реферат: Решение задачи о кратчайшем маршруте
Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:
lr1,j = lj - lr1 , (5)
где lr1,j берется из таблицы, причем lr1 выбирается так, чтобы выполнилось равенство (5). Таким образом определим r1. Далее продолжим ту же операцию, но будем считать, последней не Pn , а Pr1 . Будем продолжать до тех пор, пока rn =1.
Таким образом кратчайший маршрут проходит через Pr1 ,Pr2 ,...,Prn , а длинна маршрута Lmin=lr2,r1 +lr3,r2 +...+lrn-1,rn .
3. Описание программы.
Программа “FORD” написана на языке высокого уровня - Pascal, в интегрированной среде разработки “Turbo Pascal 7.0” фирмы Borland Inc.
Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат. Вывод результатов возможен как в файл, так и на экран.
В программе предусмотрена возможность повторного решения задачи с другими исходными данными.
4. Описание подпрограмм и процедур.
Подпрограммы и функции.
|
ТИП |
НАЗВАНИЕ |
НАЗНАЧЕНИЕ |
|
Function type : real | min; | Вычисляет минимальное значение вектора k[i]; |
| Procedure | set_graph_mode; | Устанавливает графический режим; |
| Procedure | install_firewall; | Инициализирует огонь; |
| Procedure | fire; | Процедура рисования огня; |
| Procedure | ok; | Выводит сообщение о корректности операции; |
| Procedure | notok; | Выводит сообщение о некорректности операции; |
| Procedure | check_input_data; | Проверяет корректность ввода данных; |
| Procedure | keybord_input; | Ввод исходных данных с клавиатуры; |
| Procedure | ramka; | Выводит рамку по краям экрана; |
| Procedure | save; | Сохранение результатов в файл; |
| Procedure | about_program; | Выводит информацию о программе; |
| Procedure | about_method; | Выводит информацию о методе Форда; |
| Procedure | output_graph; | Рисует вершины графа; |
| Procedure | draw_ways; | Рисует дуги графа; |
| Procedure | draw_short_way; | Рисует кратчайший маршрут; |
| Procedure | count_point_coord; | Вычисляет экранные координаты вершин графа; |
| Procedure | set_font; | Инициализирует шрифт пользователя; |
| Procedure | calculate; | Основное математическое ядро программы; |
| Procedure | draw_menu; | Открытие меню; |
| Procedure | redraw_menu; | Закрытие меню; |
| Procedure | main_menu; | Основной механизм меню; |
| Procedure | pixel; | Ставит точку; |
| Procedure | stars; | Инициализирует массив со звездами; |
| Procedure | welcomescreen; | Заставка; |
4.2 Таблица идентификаторов.
|
ИМЯ |
тИП |
НАЗНАЧЕНИЕ |
| Константы | ||
| menu | array of string | Описывает меню программы |
| menuof | array of byte | Описывает меню программы |
| menugo | array of byte | Описывает меню программы |
| name1 | string | Имя файла входных данных |
| name2 | string | Имя файла выходных данных |
| xxx | word | Размер огня по х |
| yyy | word | Размер огня по у |
| xx1 | word | Координата х огня |
| yy1 | word | Координата у огня |
| messize | byte | Размер заглавия |
| title | array of string | Заглавие |
| Переменные | ||
| mas | array of real | Основная матрица вычислений |
| coord_point | array of real | Координаты вершин графа |
| i | integer | Переменная для организации цикла |
| j | integer | Переменная для организации цикла |
| t | integer | Используется при расчете пути |
| m | integer | Счетчик кол-ва вершин в крат. Пути |
| n | integer | Кол-во вершин в графе |
| z | integer | Код ошибки |
| x1 | integer | Исп. в процедуре вывода на экран |
| y1 | integer | Исп. в процедуре вывода на экран |
| x2 | integer | Исп. в процедуре вывода на экран |
| y2 | integer | Исп. в процедуре вывода на экран |
| kk | integer | Промежуточное значение |
| iii | integer | Промежуточное значение |
| x | integer | Координата х конца отрезка |
| y | integer | Координата у конца отрезка |
| lenth | integer | Кол-во вершин в кратчайшем маршруте |
| chrus | integer | Номер шрифта пользователя |
| z1 | integer | Номер графического драйверв |
| z2 | integer | Номер графического режима |
| k | array of real | Используется для нахождения минимума |
| result | array of integer | Номера вершин, которые входят в кратчайший маршрут |
| error_code | array of byte | Коды ошибок при вводе данных |
| fire1 | array of byte | Хранит цвета огня |
| fire2 | array of byte | Матрица промежуточных данных |
| aa | real | Используется при вычислении координат вершин графа |
| pi1 | real | Используется при вычислении координат вершин графа |
| s | real | Хранит промежуточное значение |
| l | boolean | Исп. при определении кратчайшего маршрута |
| inputdata | boolean | TRUE, если данные вводились |
| calculatedata | boolean | TRUE, если данные били обработаны |
| mov | boolean | Используется в процедуре меню |
| o | string | Используется при вводе с клавиатуры |
| temp | byte | Хранит временное значение |
| cursor | byte | Координаты курсора меню |
| lastcursor | byte | Последние координаты курсора меню |
| menulevel | byte | Уровень меню |
| nline | byte | Кол-во строк в текушем уровне меню |
| pressed | char | Используется при вводе с клавиатуры |
| f1 | text | Файловая переменная |
| f2 | text | Файловая переменная |
5. Примеры решения контрольных задач.
Исходная таблица расстояний для одного из вариантов ранжированного графа:
| Pi /Pj | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | X | 5 | 3 | |||
| 2 | X | 2 | 5 | |||
| 3 | X | 7 | 7 | |||
| 4 | X | 3 | ||||
| 5 | X | 2 | ||||
| 6 | X |
После обработки таблицы с заданными исходными данными, программа выдает следующие результаты:
- кратчайший маршрут: 1-2-4-6
- длинна кратчайшего маршрута: 10
Исходная таблица расстояний для одного из вариантов не ранжированного графа:
| Pi /Pj | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | X | 1 | 6 | 2 | ||
| 2 | X | 1 | ||||
| 3 | 8 | X | ||||
| 4 | 2 | X | 5 | |||
| 5 | 1 | 3 | X | 9 | ||
| 6 | X |
После обработки таблицы с заданными исходными данными, программа выдает следующие результаты:
- кратчайший маршрут: 1-5-4-2-6
- длинна кратчайшего маршрута: 8