УДК 004.021
НАХОЖДЕНИЕ МИНИМАЛЬНОГО ПУТИ В ОРИЕНТИРОВАННЫХ ГРАФАХ
Е.И.Кудинова, студент гр. 345А;Е.О.Куренная*, студент гр. 345А
Национальный аэрокосмический университет им. Н. Е.Жуковского "ХАИ"
Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности, в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь,то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина.
Существует несколько алгоритмов нахождение кратчайшего пути в графе. Их основное отличие в количестве операций и в возможности содержать отрицательные ребра. Алгоритмы легко реализуются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется. Каждый из алгоритмов решает частную задачу о кратчайших путях на взвешенном связном графе. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, для которого сумма весов пройденных рёбер будет минимальна.
Для выполнения поставленной задачи были рассмотрены алгоритмы Флойда-Уоршелла, Форда-Беллмана, Дейкстры и алгоритм Дейкстры для разреженных графов.
Разработан программный продукт, реализующий алгоритм Флойда- Уоршалла для поиска кратчайшего пути в графе. Был выбран именно этот алгоритм, т.к. он годен для большинства графов с ребрами неотрицательной длины, а также веса ребер могут быть отрицательными. Программа позволяет для заданных пользователем номеров пунктов определить кратчайший путь.
Список использованных источников
1. Нефёдов,В.Н.Курс дискретной математики [Текст] / В. Н. Нефёдов. -Наука,1992.-321с.
Нет похожих статей