Курсовая работа: Пошук найкоротшого шляху на орієнтованому графі

Шляхом (або орієнтованим маршрутом) орієнтованого графа називається послідовність дуг, в якій кінцева вершина будь-якої дуги, відмінною від останньої, є початковою вершиною наступної.

Так, на рис. 2.1.2 шляхами є послідовності дуг: а₆ , а₅ , а₉ , а₈ , а_4. (1) а₁ , а₆ , а₅ , а₉ . (2) а₁ , а₆ , а₅ , а₉ , а₁₀ , а₆ , а₄ . (3) Орієнтованої ланцюгом (орцепью) називається такий шлях, в якому кожна дуга використовується не більше одного разу. Простим ланцюгом називається такий шлях, в якому кожна вершина використовується не більше одного разу. Наприклад, шлях (2). Маршрут є неорієнтований "двійник" шляху, і це поняття розглядається в тих випадках, коли можна знехтувати спрямованістю дуг у графі. Таким чином, маршрут є послідовність ребер ä₁ , ä₂ ,..., ä_q , в якій кожне ребро а_i , за винятком першого і останнього ребер, пов'язане з ребрами а_i-1 і а_i+1 своїми кінцевими вершинами. Послідовності дуг: ä₂ , ä₄ , ä₈ , ä₁₀ , (4) ä₂ , ä₇ , ä₈ , ä₄ , ä₃ , (5) ä₁₀ , ä₇ , ä₄ , ä₈ , ä₇ , ä₂ . (6) у графі, зображеному на рис. 2.1.2, є маршрутами; дві точки над символом дуги означають, що її орієнтацією нехтують, тобто дуга розглядається як неорієнтовані ребро. Також шлях або маршрут можна зображати послідовністю вершин. Наприклад, шлях (1) буде виглядати наступним чином: х₂ , х₅ , х₄ , х₃ , х₅ , х₆ . Іноді дуг графа приписуються числа, що називаються вагою, вартістю, або довжиною цієї дуги. У цьому випадку граф називається графом із завислими дугами. А якщо вага приписується вершин графа, то тоді виходить граф з зваженими вершинами. Якщо в графі ваги приписані і дуг і вершин, то він називається просто зваженим. При розгляді шляху μ представленого послідовністю дуг (ä₁ , ä₂ ,..., ä_q ), за його вага приймається число l (μ), яка дорівнює загальній кількості ваг всіх дуг, що входять в μ, тобто

2.2 Алгоритм Дейкстри

Алгоритм Дейкстри будує найкоротші шляхи, що ведуть з вихідної вершини графа до решти вершин цього графа (якщо такі є). У процесі роботи алгоритму послідовно позначаються розглянуті вершини графа. При чому вершина, позначена останньої (на даний момент) розташована ближче до вихідної вершині, ніж всі непозначених, але далі, ніж всі помічені. Спочатку позначається вихідна вершина; наступної, очевидно, буде позначена вершина, найближча до початкової, і суміжна з нею. Нехай на якомусь кроці вже позначені кілька вершин. Відомі найкоротші шляхи, що ведуть з вихідної вершини до поміченої. Для кожної з непозначених вершин проробимо наступне: 1. Розглянемо всі дуги, провідні з помічених вершин в одну непозначених. Кожна така дуга є останньою дугою на шляху з вихідної вершини в цю непозначену. 2. Виберемо з цих шляхів найкоротший. А потім виберемо серед них самий короткий до всіх непозначених вершин, і позначимо вершину, до якої він веде. Алгоритм завершиться, коли будуть помічені всі досяжні вершини. У результаті роботи алгоритму Дейкстри будується Дерево найкоротших шляхів.

3. ОСОБЛИВОСТІ РОБОТИ В СЕРЕДОВИЩІ

При написанні програми використовувалася середу Microsoft Visual C + + 6.0. Дане середовище дозволяє писати програми на мові C + +. У ході написання програми всі оператори і службові слова мови С + + виділяються іншим кольором, щоб відрізняти їх від змінних, заданих програмістом. Середовище Microsoft Visual C + + 6.0 містить вбудований компілятор. Вікно програми розділене на декілька частин. Вгорі знаходиться стандартна панель - Standart, з якою можна зберегти вихідний текст програми на диск, відкрити новий документ, скопіювати або вставити текст, скасувати останню дію, або знайти текст. Зліва знаходяться панелі Object TreeView і Object Inspector, на яких показані об'єкти, які використовуються в даній програмі, та їх властивості. У центрі вікна програми розташований текстовий редактор, в якому слід писати програму. Внизу - панель 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 до x_i+1 та x_i+1 до х_i вважаються рівними, а відстані від х_i до х_i - не існуючими. Якщо ребра між зазначеними вершинами не існує, введіть 0 (нуль). На екран виводиться матриця суміжності, що відображає введену інформацію. 3. Введіть номер вершини, від якої починається шуканий шлях. 4. Введіть номер вершини, у якій шлях закінчується. 5. Щоб завершити роботу програми після отримання результату натисніть Enter.

ВИСНОВОК

Таким чином, в процесі створення даного проекту розроблена програма, що реалізує алгоритм Дейкстри в Microsoft Visual C + + 6.0. Її недоліком є примітивний користувальницький інтерфейс. Це пов'язано з тим, що програма працює в консольному режимі, не додає до складності мови складність програмного віконного інтерфейсу. Також були поглиблені знання, отримані в процесі виконання лабораторних робіт з предмету «Програмування».

ПЕРЕЛІК ПОСИЛАННЯ

1. Бондарєв В.М. Програмування на С + + .- Х: «Компанія СМІТ», 2004