Читать курсовая по информатике, вычислительной технике, телекоммуникациям: "Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)" Страница 1


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХАРКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ Кафедра информатики КУРСОВАЯ РАБОТА

Тема: “Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)” по дисциплине «Программирование»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Выполнил: Руководители:

Студент группы КИ-05-4 Руденко Д. А.

Петров О. В. Машталир С. В. Харьков 2006

РЕФЕРАТ Записка объяснительная к курсовой работе: 23с., 5 рис., 1 табл., 5 разделов, 3 приложения.

Объект исследования – граф с взвешенными дугами.

Цель работы – разработка демонстрационной программы использования алгоритма Дейкстры.

Метод исследования – изучение литературы, составление и отладка программы на компьютере.

Данную программу можно использовать для поиска кратчайших расстояний между двумя точками.

Программа составлена на языке С++ в среде Microsoft Visual C++ 6.0. Ключевые слова:АЛГОРИТМ ДЕЙКСТРЫ, ГРАФ, ВЕРШИНА, РЕБРО, ВЕС, ПУТЬ, МАССИВ, МЕТКА, ПРОГРАММА, ТИП, ОПЕРАТОР, ФУНКЦИЯ, ЦИКЛ, МАТРИЦА СМЕЖНОСТИ.

СОДЕРЖАНИЕ

Введение………………………………………………………....……

4

1 Постановка задачи и сфера её применения…..………………......

6

2 Теоретическая часть…………………………………….……….....

7

2.1 Общие сведения о графах……………………………...…….

7

2.2 Алгоритм Дейкстры….……………………………………...

9

3 Особенности работы в среде ……………………….…………….

10

4 Программная реализация………………………………….…….

11

4.1 Описание алгоритма и структуры программы……………..

11

4.2 Описание программных средств…………………………….

13

5 Инструкция пользователя………………………………………….

15

Заключение….…………………………………………………….….

16

Перечень ссылок……………………………………………………...

17

Приложение А Текст программы…………………………………..

18

Приложение Б Результат………..……………………………….…..

22

Приложение В Схема программной реализации алгоритма Дейкстры…..

23

ВВЕДЕНИЕ Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.

Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:

    алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами); алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин); алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).

Указанные алгоритмы



Интересная статья: Быстрое написание курсовой работы