Нахождение кратчайшего маршрута в графе с помощью алгоритма Дейкстры
Курсовая работа, 12 Июня 2013, автор: пользователь скрыл имя
Описание работы
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).
Файлы: 1 файл
Пояснительная записка «Нахождение кратчайшего маршрута в графе с.doc
— 446.00 Кб (Скачать файл)
Для того чтобы просчитать путь нужно:
- Создать или загрузить из файла матрицу смежности.
- Отобразить граф случайными или круговыми координатами, если что то не устраивает вершины можно двигать.
- Выставить из какой в какую вершину нужно найти путь над кнопкой Path.
- Нажать кнопку Path.
Вывод
Было разработано приложение позволяющее любому человеку просчитать кратчайший путь из одного места в другое например если он путешествует на машине, или просто занимается какими то исследования в области теории графов.
Список литературы
- «Программирование в Алгоритмах» Окулов
- http://wikipedia.org/
- http://algolist.ru/