МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
В В
Кафедра інформатики
В В В
Курсова робота
Тема: "Програмна реалізація алгоритму Дейкстри (побудова ланцюгів мінімальною довжини) "
В
з дисципліни В«ПрограмуванняВ»
В В
Пояснювальна записка
В В
Виконав: Керівники:
Студент групи КІ-05-4 Руденко Д. А.
Петров О. В. Машталір С. В.
В В В
Харків 2006
РЕФЕРАТ
Записка пояснювальна до курсової роботи: 23с., 5 рис., 1 табл., 5 розділів, 3 додатки.
Об'єкт дослідження - граф з зваженими дугами.
Мета роботи - розробка демонстраційної програми використання алгоритму Дейкстри.
Метод дослідження - вивчення літератури, складання та налагодження програми на комп'ютері.
Дану програму можна використовувати для пошуку найкоротших відстаней між двома точками.
Програма складена на мові С + + в середовищі Microsoft Visual C + + 6.0. Ключові слова: алгоритм Дейкстри, ГРАФ, ВЕРШИНА, РЕБРО, ВЕС, ШЛЯХ, МАСИВ, МІТКА, ПРОГРАМА, ТИП, ОПЕРАТОР, ФУНКЦІЯ, ЦИКЛ, матриці суміжності. br clear=all>
ЗМІСТ
Введення .........................................................................
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 і т.п.
Найкоротший шлях розглядається за допомогою деякого математичного об'єкта, званого графом. p> Існують три найбільш ефективних алгоритму знаходження найкоротшого шляху:
В· алгоритм Дейкстри (використовується для знаходження оптимального маршруту між двома вершинами);
В· алгоритм Флойда (для знаходження оптимального маршруту між усіма парами вершин);
В· алгоритм Єна (для знаходження k-оптимальних маршрутів між двома вершинами).
Зазначені алгоритми легко виконуються при малій кількості вершин у рядку. При збільшенні їх кількості завдання пошуку найкоротшого шляху ускладнюється. Тут на допомогу приходить сучасна техніка
Комп'ютерні засоби та інформаційні технології підвищили можливості такого всеосяжного методу вивчення і створення, як моделювання об'єктів, явищ і процесів - як тих, що існують в природі, так і тих, що створюються людиною штучно.
Кількість об'єктів ускладнювалися, збільшувалися, і натурне моделювання (макети споруд) стал...
