шлях, а також висновок довжини маршруту. Якщо шляху між заданими точками НЕ існує - виводиться відповідне повідомлення.
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)
Масив ij елемент якого містить відстань між 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. Введіть кількість вершин досліджуваного графа. p> 2. Введіть ваги ребер (позитивне число). У програмі відстані від х i до x i +1 і x i +1 до х i вважаються рівними, а відстані від х i до х i - Не існуючими. Якщо ребра між зазначеними вершинами не існує, введіть 0 (нуль).
На екран виводиться матриця суміжності, що відображає введену інформацію.
3. Введіть номер вершини, від якої починається шуканий шлях.
4. Введіть номер вершини, у якій шлях закінчується.
5. Щоб завершити роботу програми після отримання результату натисніть Enter.
ВИСНОВОК
Таким чином, в процесі створення даного проекту розроблена програма, що реалізує алгоритм Дейкстри в Microsoft Visual C + + 6.0. Її недоліком є примітивний користувача інтерфейс. Це пов'язано з тим, що програма працює в консольному режимі, не додавайте до складності мови складність програмного віконного інтерфейсу
Також були поглиблені знання, отримані в процесі виконання лабораторних робiт по предмету В«ПрограмуванняВ».
ПЕРЕЛІК ПОСИЛАНЬ
1. Бондарєв В.М. Програмування на С + +.-Х: В«Компанія СМІТВ», 2004
2. Страуструп Бьярн Мова програмування С + + (2 год). - В«К: ДіаСофтВ», 1993
3. Хаханов В.І., Чумаченко С.В. Дискретна математика (теоретичне і практичне зміст курсу).-Кафедра АПОТ, 2002
4. Алгоритм Дейкстри
5. Конспект лекцій.
В
Додаток А
Текст програми
# include
# include
# include
# include
# include
# define word unsigned 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;
fo...
