МІНІСТЕРСТВО освіти и науки України
Національний университет В«Львівська ПолітехнікаВ»
Кафедра автоматизованих систем Управління
Курсова робота
з дісціпліні В«Проблемно-орієнтовані мови програмуванняВ»
на тему
Поиск найкоротшого шляху на орієнтованому графі
Виконала:
Студент групи КН-22з
Василашко Володимир
Керівник:
Кустра Н.О.
Львів 2011
МІНІСТЕРСТВО освіти та науки України
Національний университет В«Львівська політехнікаВ»
Кафедра автоматизованих систем Управління
Завдання на курсову роботу
з дісціпліні В«Проблемно-орієнтовні мови програмуванняВ»
Прізвище, Ім'я студента Василашко Володимир
Група КН-22з
Тема курсової роботи Поиск найкоротшого шляху на орієнтованому графі
Зміст
Вступ
1.Постановка Завдання та сфера її застосування
2. Теоретична частина
2.1 Загальні Відомості про графіч
2.2 Алгоритм Дейкстри
3. Особливості роботи в середовіщі
4. Програмное реалізація
4.1 Опис алгоритму та структури Програми
4.2 Опис програмних засобів
5. Інструкція користувача
Висновок
Перелік посилання
Додаток А Текст Програми
Додаток Б Результат
Додаток В Схема програмної реалізації алгоритму Дейкстри
ВСТУП
Завдякі своєму широкому застосуванню, теорія про знаходження найкоротшіх Шляхів останнім годиною інтенсівно розвівається. Знаходження найкоротшого шляху - життєво необхідно и вікорістовується практично Скрізь, починаючі від перебування оптимального маршруту Між двома об'єктами на місцевості (Наприклад, найкоротшій шлях від Будинку до універсітету), в системах автопілота, для знаходження оптимального маршруту при перевезені, комутації інформаційного пакету в Internet и т.д. Найкоротшій шлях розглядається за допомог Певного математичного об'єкту, званого графом. Існують три найбільш ефективних алгоритмом знаходження найкоротшого шляху:
• алгоритм Дейкстри (вікорістовується для знаходження оптимального маршруту Між двома вершинами);
• алгоритм Флойда (для знаходження оптимального маршруту Між усіма парами вершин);
• алгоритм Йена (перебування k-оптимальних маршрутів Між двома вершинами).
Зазначені алгоритм легко виконують при Малій кількості вершин у графі. При збільшенні їх кількості Завдання Поиск найкоротшого шляху ускладнюється. Тут на допомог приходити сучасна техніка. Комп'ютерні засоби та Інформаційні технології підвіщілі возможности такого всеосяжного методу Вивчення и Створення, Як моделювання об'єктів, явищем и процесів - Як тихий, Що існують у природі, так и тихий, Що створюються Людиною штучно. Кількість об'єктів ускладнюваліся, збільшуваліся, и натурних моделювання (макети споруд) стало невігіднім, не Економні. Тому для Вивчення Почаїв застосовуваті математику. Використання математичних моделей - рівняння, нерівності, формули и того подібне назівається математичного Моделювання, для розвітку и прістосування Якого Потрібні булі ефектівні чісельні методи. Реалізуваті великий Потенціал математичного моделювання Неможливо без Потужной засобів автоматізації обчисления, якімі є комп'ютери. Завдякі появі комп'ютерів и розвітку інформаційніх технологій створюються методи та засоби комп'ютерного моделювання, здатні вірішуваті складні Практичні Завдання, Такі Як Управління великими ЕНЕРГЕТИЧНА системами, Створення достовірніх прогнозів постривай або врожаю, моделювання регіональніх и загальнодержавного систем, проектування літаків, кораблів ТОЩО. Комп'ютерна модель - Ції розміщена в комп'ютері сукупність засобів, Що реалізують концепцію обчислення. Для реалізації комп'ютерної Моделі, Велике значення має такий науковий напрямок, Як програмування. Без нього комп'ютер це просто набор різніх прістроїв, мікросхем, Який НЕ Може буті корисностей. Великі Програми Із-за своєї складності нерідко містять помилки, які можут стати причиною матеріальних збитків, а іноді й загрожуваті життю людей (Наприклад, при управлінні авіапольотом). У результаті боротьбі з проблемою складності програмного коду булі віроблені три Нові Концепції програмування: а) об'єктно-орієнтоване програмування (ООП), б) уніфікована мова моделювання (UML); в) спеціалізовані засоби розробка програмного забезпечення; З усіх об'єктно-орієнтованих мов С + + є найбільш широко вікорістовуванім. І самє з Його допомога У даного курсового проекті реалізується алгоритм Дейкстри.
1. ПОСТАНОВКА Завдання І СФЕРА ЇЇ ЗАСТОСУВАННЯ
Основним Завдання даного курсового проекту є програмное реалізація алгоритму Поиск найкоротшого шляху Між двома будь-якімі вершинами графа. Програма повинна працюваті так, щоб користувач вводів кількість вершин и довжина ребер графа, а після ОБРОБКИ ціх даніх на екран віводівся найкоротшій шлях Між двома завданні вершинами и Його довжина. Необхідно передбачіті Різні Результати пошуку, щоб программа НЕ відавала помилок и працювала правильно. Дана програма Може вікорістовуватіся в діскретної математики для Дослідження графів або в ЯКОСТІ наочно посібніка, Що демонструє застосування алгоритму Дейкстри на практіці. Алгоритм Дейкстри граф найкоротшій шлях
2. Теоретичність ЧАСТИНА
2.1 Відомості про графіч
Граф G (ріс.2.1.1) задається множини точок (вершин) х 1 , х 2 , ..., х n . (Яке позначається через Х) i безліччю ліній (ребер) а 1 , а 2 , ..., а m . (Яке позначається символом А), Що з'єднують Між собою ВСІ або Частину ціх точок. Таким чином, граф G повністю задається (і позначається) парою (Х, А). ЯКЩО ребра з множини А орієнтовані, Що зазвічай показується стрілкою, то смороду назіваються дугами, и граф з такими ребрами назівається орієнтованім графом.
Ріс.2.1.1
Ріс.2.1.2
Наприклад, ЯКЩО дорога має НЕ двохсторонній, а односторонній Рух то напрямок цього руху буде показано стрілкою. ЯКЩО ребра не мают орієнтації, то граф назівається неорієнтованім, (двосторонній рух). У орієнтованому графі дуга позначається впорядкованої парою, Що Складається з початкової та кінцевої вершин, її напрямок передбачається завданні от Першої вершини до Другої.
Шляхом (або орієнтованім маршрутом) орієнтованого графа назівається послідовність дуг, в якій кінцева вершина будь-якої дуги, відмінною від останньої, є початково вершиною наступної.
Так, на рис. 2.1.2 шляхами є послідовності дуг: а 6 , а 5 , а 9 , а 8 , а 4. (1) а 1 , а 6 , а 5 , а 9 . (2) а 1 , а 6 , а 5 , а 9 , а 10 , а 6 , а 4 . (3) орієнтованої ланцюг (орцепью) назівається такий шлях, в якому Кожна дуга вікорістовується НЕ Більше одного разу. Пробачимо ланцюг назівається такий шлях, в якому Кожна вершина вікорістовується НЕ Більше одного разу. Наприклад, шлях (2). Маршрут є неорієнтованій "двійнік" шляху, и Це Поняття розглядається в тихий випадка, коли можна знехтуваті спрямованістю дуг у графі. Таким чином, маршрут є послідовність ребер Г¤ 1 , Г¤ 2 , ..., Г¤ q , в якій кожне ребро а < sub> i , за вінятком Першого и последнего ребер, пов'язане з ребрами а i-1 и а i +1 Своїми кінцевімі вершинами. Послідовності дуг: Г¤ 2 , Г¤ 4 , Г¤ 8 , Г¤ 10 , (4) Г¤ 2 , Г¤ 7 , Г¤ 8 , Г¤ 4 , Г¤ 3 , (5) Г¤ 10 , Г„ 7 , Г¤ 4 , Г¤ 8 , Г¤ 7 , Г„ 2 . (6) у графі, збережений на рис. 2.1.2, є м...
