Реферат "Решение задачи о кратчайшем маршруте"

Название:
Решение задачи о кратчайшем маршруте
Тип работы:
Реферат
Размер:
33.4 КБ
65
Скачать

Необходимо определить кратчайший маршрут из пункта P1 в P6. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.

Постановка задачи приобретает смысл в том случае, если имеется несколько вариантов маршрута из начального пункта в конечный. В этом случае физический смысл функции цели задачи состоит в минимизации общей длинны маршрута, т.е. в определении кратчайшего пути из P1 в Pn.

Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат. Вывод результатов возможен как в файл, так и на экран.

Составлена программа на алгоритмическом языке высокого уровня “Pascal”, позволяющая решать задачу в диалоговом режиме, удобном для пользователя не программиста.

Алгоритм решения транспортной задачи методом Форда является универсальным, что позволяет производить расчёты как с ранжированными, так и с не ранжированными графами (примеры решения задачи приведены на странице 11).