Міністерствоосвіти і науки України
Національнийуніверситет «Львівська Політехніка»
Кафедраавтоматизованих систем управління
Курсоваробота
здисципліни «Проблемно-орієнтовані мови програмування»
натему
Пошукнайкоротшого шляху на орієнтованому графі
Виконав:
Студентгрупи КН-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. (Якепозначається через Х) і безліччю ліній (ребер) а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, в якій кожне ребро а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, є маршрутами; дві точки над символом дугиозначають, що її орієнтацією нехтують, тобто дуга розглядається якнеорієнтовані ребро. Також шлях або маршрут можна зображати послідовністювершин. Наприклад, шлях (1) буде виглядати наступним чином: х2,х5, х4, х3, х5, х6. Іноді дуг графа приписуютьсячисла, що називаються вагою, вартістю, або довжиною цієї дуги. У цьому випадкуграф називається графом із завислими дугами. А якщо вага приписується вершинграфа, то тоді виходить граф з зваженими вершинами. Якщо в графі ваги приписаніі дуг і вершин, то він називається просто зваженим. При розгляді шляху μ представленогопослідовністю дуг (ä1, ä2,...,äq), зайого вага приймається число l (μ), яка дорівнює загальній кількості вагвсіх дуг, що входять в μ, тобто
/>
2.2 Алгоритм Дейкстри
Алгоритм Дейкстри будує найкоротші шляхи, що ведуть з вихідної вершиниграфа до решти вершин цього графа (якщо такі є). У процесі роботи алгоритмупослідовно позначаються розглянуті вершини графа. При чому вершина, позначенаостанньої (на даний момент) розташована ближче до вихідної вершині, ніж всінепозначених, але далі, ніж всі помічені. Спочаткупозначається вихідна вершина; наступної, очевидно, буде позначена вершина,найближча до початкової, і суміжна з нею. Нехай на якомусь кроці вже позначенікілька вершин. Відомі найкоротші шляхи, що ведуть з вихідної вершини до поміченої.Для кожної з непозначених вершин проробимо наступне: 1. Розглянемо всі дуги, провідні з помічених вершин водну непозначених. Кожна така дуга є останньою дугою на шляху з вихідноївершини в цю непозначену. 2. Виберемо зцих шляхів найкоротший. А потім виберемо серед них самий короткий до всіхнепозначених вершин, і позначимо вершину, до якої він веде. Алгоритмзавершиться, коли будуть помічені всі досяжні вершини. У результаті роботиалгоритму Дейкстри будується Дерево найкоротших шляхів.
3. ОСОБЛИВОСТІ РОБОТИ В СЕРЕДОВИЩІ
При написанні програми використовувалася середуMicrosoft Visual C + + 6.0. Дане середовище дозволяє писати програми на мові C+ +. У ході написання програми всі оператори і службові слова мови С + +виділяються іншим кольором, щоб відрізняти їх від змінних, заданихпрограмістом. Середовище Microsoft Visual C + + 6.0 містить вбудованийкомпілятор. Вікно програми розділене на декілька частин. Вгорі знаходитьсястандартна панель — Standart, з якою можна зберегти вихідний текст програми надиск, відкрити новий документ, скопіювати або вставити текст, скасувати останнюдію, або знайти текст. Зліва знаходяться панелі Object TreeView і ObjectInspector, на яких показані об'єкти, які використовуються в даній програмі, таїх властивості. У центрі вікна програми розташований текстовий редактор, вякому слід писати програму. Внизу — панель Output, в якій показуєтьсяповідомлення, якщо в програмі містяться помилки — компілятор повідомляє видпомилки і рядок, в якій вона допущена, досить зробити подвійний клік лівоюклавішею миші на описі помилки в Output, щоб переміститися на рядок, що міститьпомилки. Програма створена в консольному режимі — в режимі, що не маєграфічного інтерфейсу.
4 ПРОГРАМНАРЕАЛІЗАЦІЯ
4.1 Описалгоритму та структури програми
/>
Рис.4.1.1
Програма виводить мінімальний шлях між двома зазначенимивершинами у графі і його довжину. При запуску програми на екран виводитьсязапит про введення ваг ребер досліджуваного графа. Дані,введені користувачем, відображаються у вигляді матриці суміжності, в якій неіснуючі ребра позначаються нулями. Післязазначеним ребрах присвоюється значення 65535, яке приймається занескінченність. Наступним етапом виконання програми є запит про введенняномерів вершин, між якими необхідно дізнатися шлях. У випадку, якщо початковата кінцева вершини співпадають, з'являється повідомлення і робота програмизавершується. В іншому випадку виконується безпосередньо алгоритм Дейкстри,схема якого наведена у додатку В. Результатом програми є вивід на екран вершин,через які проходить мінімальний шлях, а також виведення довжини маршруту. Якщошляху між заданими точками не існує — виводиться відповідне повідомлення.
4.2 Описвикористаних програмних засобів
Таблица 4.2.1–ОписзміннихЗмінна Тип Опис n int Кількість точок (вершин) графа i,j int Лічильники p int Номер найкоротшого шляху і найменшої довжини шляху xn int Номер початкової точки (вершини) xk int Номер кінцевої точки (вершини) flag[11] int Масив, i-й елемент якого має значення 0, коли i-й шлях і відстань тимчасові, і приймає значення 1, коли i-й шлях і відстань стають постійними c[11][11] word (unsigned int)
Масив i-j елемент якого містить відстань між i-й і j-й крапками (вершинами)Зауваження:
1. с[i][i]=¥
2. c[i][j]=c[j][i] s[80] char Рядкова змінна, яка містить проміжні значення шляху path[80][11] char Масив рядків, який містить шляхуЗауваження: Після проходження обробки за алгоритмом Дейкстри p-й елемент масиву містить найкоротший шлях. l[11] word (unsigned int) Масив, який містить довжини шляхів (path)Зауваження: Після проходження обробки за алгоритмом Дейкстри p-й елемент масиву містить довжину найкоротшого шляху.
Крім стандартнихфункцій з бібліотек iostream.h, string.h, stdio.h, conio.h були використанітакож наступні функції.• word minim (word x, word y) — функція, яка повертаємінімальне з x і y.
/>
Рис.4.2.1
• int min (int n)- функція, яка повертає номер елемента масиву l [i] мінімальної «невідмічений»довжиною шляху (flag [i] = 0).
/>
Рис.4.2.2
5. ІНСТРУКЦІЯ КОРИСТУВАЧА
При запуску програми на екрані з'явиться вікно зінструкціями. Виконуйте ці інструкції, а саме: 1. Введіть кількість вершин досліджуваного графа. 2.Введіть ваги ребер (позитивне число). У програмівідстані від хi до xi+1 та xi+1 до хi вважаються рівними, а відстані від хi до хi — не існуючими. Якщо ребра міжзазначеними вершинами не існує, введіть 0 (нуль). На екран виводиться матрицясуміжності, що відображає введену інформацію. 3. Введіть номер вершини, від якої починається шуканий шлях. 4. Введіть номер вершини, у якій шлях закінчується. 5.Щоб завершити роботу програми після отриманнярезультату натисніть Enter.
ВИСНОВОК
Таким чином, в процесі створення даного проектурозроблена програма, що реалізує алгоритм Дейкстри в Microsoft Visual C + +6.0. Її недоліком є примітивний користувальницький інтерфейс. Це пов'язано зтим, що програма працює в консольному режимі, не додає до складності мовискладність програмного віконного інтерфейсу. Також були поглиблені знання,отримані в процесі виконання лабораторних робіт з предмету «Програмування».
ПЕРЕЛІК ПОСИЛАННЯ
1. Бондарєв В.М. Програмування на С ++ .- Х: «Компанія СМІТ», 2004
2. Страуструп Бьярн Мовапрограмування С + + (2 рік) .- «К: ДіаСофт», 1993
3. Хаханов В.І., Чумаченко С.В.Дискретна математика (теоретичне І практичне Зміст курсу) .- Кафедра АПОТ, 2002
4. Алгоритм Дейкстри
5. Конспект лекцій.
Додаток А
Текст програми
#include
#include
#include
#include
#include
#define wordunsigned int
int i, j, n, p,xn, xk;
int flag[11];
word c[11][11],l[11];
char s[80],path[80][11];
int min(int n)
{
int i, result;
for(i=0;i
if(!(flag[i]))result=i;
for(i=0;i
if((l[result]>l[i])&&(!flag[i]))result=i;
return result;
}
word minim(wordx, word y)
{
if(x
return y;
}
void main()
{
cout
cin>>n;
for(i=0;i
for(j=0;j
for(i=0;i
for(j=i+1;j
{
cout
cin>>c[i][j];
}
cout
for(i=0;i
cout
for(i=0;i
{
printf(«X%d»,i+1);
for(j=0;j
{
printf("%6d",c[i][j]);
c[j][i]=c[i][j];
}
printf("\n\n");
}
for(i=0;i
for(j=0;j
if(c[i][j]==0)c[i][j]=65535; //безкінечнність
cout
cin>>xn;
cout
cin>>xk;
xk--;
xn--;
if(xn==xk)
{
cout
getch();
return;
}
for(i=0;i
{
flag[i]=0;
l[i]=65535;
}
l[xn]=0;
flag[xn]=1;
p=xn;
itoa(xn+1,s,10);
for(i=1;i
{
strcpy(path[i],«X»);
strcat(path[i],s);
}
do
{
for(i=0;i
if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
{
if(l[i]>l[p]+c[p][i])
{
itoa(i+1,s,10);
strcpy(path[i+1],path[p+1]);
strcat(path[i+1],"-X");
strcat(path[i+1],s);
}
l[i]=minim(l[i],l[p]+c[p][i]);
}
p=min(n);
flag[p]=1;
}
while(p!=xk);
if(l[p]!=65535)
{
cout
cout
}
else
cout
getch();
}
Додаток Б
Результат/>
Додаток В
Схема програмноїреалізації алгоритму Дейкстри
/>