Вопрос 34

Содержание

Введение 3

1. Основные понятия 3

1.1 Актуальность алгоритма Дейкстры 3

1.2. Постановка задачи 3

1.3. Описание метода решения задач 3

2. Моделирование, оптимизация, программная реализация 3

2.1 Математическая модель 3

2.3 Программная реализация 3

Заключение 3

Список использованной литературы 3

Приложение 1 3

Введение

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

Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторика, Алгоритм на графах, изобретён нидерландским ученым Э. Дейкстрой в 1959 год его алгоритм был рассчитан для нахождения минимального пути положительных чисел, и был назван в его честь алгоритм Дейкстры. Графы стали использоваться при построении схем электрических цепей и молекулярных схем.

Однако алгоритм Дейкстры не является единственным, так же были разработаны следующие алгоритмы:

• алгоритм Беллмана-Форда

• алгоритм поиска А*

• алгоритм Флойда-Уоршелла

• алгоритм Ли (волновой алгоритм)

Каждый из перечисленных алгоритмов позволяет выполнить поиск кратчайшего пути между двумя объектами. Поиск кратчайшего пути - является жизненно необходимым, в следствии чего используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности, в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.