о невигідним, неекономним. Тому для вивчення почали застосовувати математику. Використання математичних моделей - рівняння, нерівності, формули тощо називається математичним моделюванням, для розвитку і пристосування якого потрібні були ефективні чисельні методи.
Реалізувати великий потенціал математичного моделювання неможливо без потужних засобів автоматизації обчислень, якими є комп. Завдяки появі комп'ютерів і розвитку інформаційних технологій створюються методи і засоби комп'ютерного моделювання, здатні вирішувати складні практичні завдання, такі як управління великими енергетичними системами, створення достовірних прогнозів погоди або врожаю, моделювання регіональних і загальнодержавних систем, проектування літаків, кораблів і т. п. Комп'ютерна модель - це розміщена в комп'ютері сукупність засобів, що реалізують концепцію обчислення.
Для реалізації комп'ютерної моделі, велике значення має таке науковий напрямок, як програмування. Без нього комп'ютер це просто набір різних пристроїв, мікросхем, який не може бути корисним.
Великі програми через свою складність нерідко містять помилки, які можуть стати причиною матеріальних збитків, а іноді і загрожувати життя людей (наприклад, при управлінні авіапольотом). В результаті боротьби з проблемою складності програмного коду були вироблені три нові концепції програмування:
а) об'єктно-орієнтоване програмування (ООП);
б) уніфікована мова моделювання (UML);
в) спеціалізовані засоби розробки програмного забезпечення;
З усіх об'єктно-орієнтованих мов С + + є найбільш широко використовуваним. І саме з його допомогою в цьому курсовому проекті реалізується алгоритм Дейкстри.
1 ПОСТАНОВКА ЗАВДАННЯ І СФЕРА ЇЇ ЗАСТОСУВАННЯ
Основний завданням даного курсового проекту є програмна реалізація алгоритму пошуку найкоротшого дорозі між двома будь-якими вершинами графа.
Програма повинна працювати таким чином, щоб користувач вводив кількість вершин і довжини ребер графа, а після обробки цих даних на екран виводився найкоротший шлях між двома заданими вершинами і його довжина. Необхідно передбачити різні результати пошуку, щоб програма не видавала помилок і працювала правильно.
Дана програма може використовуватися в дискретної математики для дослідження графів або в якості наочного посібника, який демонструє застосування алгоритму Дейкстри на практиці. p> 2 ТЕОРЕТИЧНА ЧАСТИНА
2.1 Відомості про графах
В
Граф G (рис.2.1.1) задається безліччю точок ( вершин ) х 1 , х 2 , ..., х n . (Яке позначається через Х) і безліччю ліній ( ребер ) а 1 , а 2 , ..., а m . (Який позначається символом А), що з'єднують між собою всі або частину цих точок. Таким чином, граф G повністю задається (і позначається) парою (Х, А). Якщо ребра з множини А орієнтовані, що зазвичай показується стрілкою, то вони називаються дугами , і граф з такими ребрами називається орієнтованим графом.
ріс.2.1.2
рис.2.1.1
br/>
Наприклад, якщо дорога має не двох-, а односторонній рух то напрямок цього руху буде показано стрілкою.
Якщо ребра не мають орієнтації, то граф називається неорієнтованим , (Двосторонній рух). p> У орієнтованому графі дуга позначається впорядкованої парою, що складається з початковій і кінцевої вершин, її напрямок передбачається заданим від першої вершини до другої. p> Шляхом (або орієнтованим маршрутом ) орієнтованого графа називається послідовність дуг, в якій кінцева вершина всякої дуги, відмінною від останньої, є початковою вершиною наступної.
Так, на рис. 2.1.2 шляхами є послідовності дуг:
а 6 , а 5 , а 9 , а 8 , а 4 . (1)
а 1 , а 6 , а 5 , а 9 . (2)
а 1 , а 6 , а 5 , а 9 , а 10 , а 6 , а 4 . (3)
Орієнтованої ланцюгом (Орцепью) називається такий шлях, в якому кожна дуга використовується не більше одного разу.
Простий орцепью називається такий шлях, в якому кожна вершина використовується не більше одного разу. Наприклад, шлях (2). p> Маршрут є неорієнтований "двійник" шляху, і це поняття розглядається в тих випадках, коли можна знехтувати спрямованістю дуг у графі. Таким чином, маршрут є послідовність ребер Г¤ 1 , ...
