Департамент освіти міста Нижній Новгород
Державна освітня установа
вищої професійної освіти
НИЖЕГОРОДСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
ім. Р.Є. Алексєєва
Курсова робота
Тема роботи: «Розробка програмного забезпечення для реалізації алгоритму Дейкстри»
по предмету Методи оптимізації
Виконав: Шамов Андрій Євгенович, група 25-ВМ
г. Нижній Новгород - 2 010 г
ЗМІСТ
1. Постановка завдання
. Введення
. Теоретична частина
. 1 Загальні відомості про графах
. 2 Опис принципу роботи алгоритму
. 3 Приклад виконання алгоритму Дейкстра
. Реалізація програмного забезпечення
. 1 Алгоритм для програмної реалізації завдання
. 2 середу розробки програмного забезпечення
. Опис роботи програми
. 1 Приклади роботи програми
. 2 Обробка помилок
Висновок
Список використовуваних ресурсів і літератури
Додаток (код програми)
ПОСТАНОВКА ЗАВДАННЯ
алгоритм Дейкстри програмний граф
Завданням даного курсового проекту є розробка програмного забезпечення для реалізації алгоритму, що дозволяє знаходити найкоротша відстань від однієї з вершин графа до всіх інших, за умови, що ребра графа не мають негативного ваги (алгоритму Дейкстри).
ВСТУП
Алгоритм Дейкстри був винайдений нідерландським вченим Е? дсгером Ві? бе Де? йкстра в 1959 році. Цей алгоритм дозволяє знаходити найкоротша відстань від однієї з вершин графа до всіх інших, за умови, що ребра графа не мають негативного ваги.
Завдання знаходження оптимального шляху актуальна у всі часи. Найбільш часте застосування сій алгоритм знаходить при знаходження оптимальних транспортних маршрутів між декількома об'єктами. Так само він широко застосовується в інформаційних технологіях, наприклад в протоколі маршрутизації OSPF для усунення кільцевих маршрутів або для оптимальної комутації пакетів в глобальній мережі.
Якщо в графі використовуються ребра з негативним вагою, тоді необхідно використовувати інші алгоритми, наприклад Алгоритм Беллмана - Форда.
3. ТЕОРЕТИЧНА ЧАСТИНА
3.1 Загальні відомості про графа
Для реалізації алгоритму необхідно використовувати граф. У математичній теорії графів lt; # 84 src= doc_zip1.jpg / gt; lt; # 155 src= doc_zip2.jpg / gt; lt; # 155 src= doc_zip3.jpg / gt;
Рис. 2
Мінімальну мітку має вершина 1. Її сусідами є вершини 2, 3 і 6. Перший по черзі сусід вершини 1 - вершина 2, тому що довжина шляху до неї мінімальна. Довжина шляху в неї через вершину 1 дорівнює сумі найкоротшої відстані до вершини 1, значення її мітки, і довжини ребра, що йде з перших в другому, тобто 0 + 7=7. Це менше поточної мітки вершини 2, нескінченності, тому нова мітка 2-й вершини дорівнює 7.
Рис. 3
Аналогічну операцію проробляємо з двома іншими сусідами 1-й вершини - третій і 6-й (рис. 3). На цьому етапі всі сусіди вершини 1 перевірені. Поточне мінімальна відстань до вершини 1 вважається остаточним і перегляду не підлягає (те, що це дійсно так, уперше довів Е. Дейкстра lt; # 155 src= doc_zip5.jpg / gt;
Рис. 4
Ще один сусід вершини 2 - вершина 4. Якщо йти в неї через 2-ю, то довжина такого шляху буде дорівнює сумі найкоротшого відстань до другого вершини і відстані між вершинами 2 і 4, тобто 22 (7 + 15 =22). Оскільки 22 lt ;, встановлюємо мітку вершини 4 рівний 22.
Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і помічаємо її як відвідану (рис. 5).
Рис. 5
Третій крок. Повторюємо крок алгоритму, вибравши вершину 3. Після її «обробки» отримаємо такі результати:
Рис. 6
Подальші кроки. Повторюємо крок алгоритму для залишилися вершин. Це будуть вершини 6, 4 і 5, відповідно до порядку.
Рис. 7
Завершення виконання алгоритму. Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видний на останньому малюнку: найкоротший шлях від вершини 1 до 2-й становить 7, до третього - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
4. РЕАЛІЗАЦІЯ ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ
Для програмної реалізації ...
