Реферат Розробка програмного забезпечення для реалізації алгоритму Дейкстри

Тема: Курсовые проекты

алгоритму задача була формалізована вигляді алгоритму.

Для позначення були використані наступні змінні:

ПеременнаяТіпОпісаніеnintКолічество точок (вершин) графаi, jintСчётчікіpintНомер найкоротшого шляху і найменшої довжини путіxnintНомер початкової точки (вершини) xkintНомер кінцевої точки (вершини) flag [1001] intМассів, i-й елемент якого має значення 0, коли i-й шлях і відстань тимчасові, і приймає значення 1, коли i-й шлях і відстань стають постоянниміc [+1001] [+1001] word (unsigned int) Масив ij елемент якого містить відстань між i-й і j-й крапками (вершинами) Зауваження: з [i] [i] =? c [i] [j]=c [j] [i] s [+8000] charСтрочная змінна, яка містить проміжні значення путіpath [+8000] [1001] charМассів рядків, який містить шляху Зауваження: Після проходження обробки за алгоритмом Дейкстри p-й елемент масиву містить найкоротший путь.l [1 001] word (unsigned int) Масив, який містить довжини шляхів (path) Зауваження: Після проходження обробки за алгоритмом Дейкстри p-й елемент масиву містить довжину найкоротшого шляху. Таблиця 1

4.1 АЛГОРИТМ ДЛЯ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ ЗАВДАННЯ

схема 1

На схемі 1 зображена блок-схема роботи програми. Блок оброблювальний алгоритм Дейкстри називається Алгоритм Дейкстри (к.о.) Його докладний алгоритм представлений нижче, на схемі 2.

Схема 2

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

Наступним етапом виконання програми є запит про введення номерів вершин, між якими необхідно дізнатися шлях. У випадку, якщо початкова та кінцева вершини співпадають, відображається відповідне повідомлення і робота програми завершується. В іншому випадку виконується безпосередньо алгоритм Дейкстри, схема якого наведена в додатку В.

Результатом програми є вивід на екран вершин, через які проходить мінімальний шлях, а також висновок довжини маршруту. Якщо шляху між заданими точками не існує - виводиться відповідне повідомлення.

Крім стандартних функцій з бібліотек були використані також наступні функції: minim (word x, word y) - функція, яка повертає мінімальне з x і y.

схема 3min (int n) - функція, яка повертає номер елемента масиву l [i] мінімальної «невідмічений» довжиною шляху (flag [i]=0).

схема 4

4.2 середу Розробка програмного забезпечення

Як середовище для розробки програмного забезпечення була обрана Microsoft Visual Studio Express 2008, кошти Visual C ++. Microsoft Visual Studio Express - лінійка безкоштовних lt; # 253 src= doc_zip18.jpg / gt;

Рис. 8

. Після завершення завдання програма запропонує повторити операцію розрахунку (те ж саме програма може запропонувати після деяких помилок введення даних).

5.1 ПРИКЛАДИ РОБОТИ ПРОГРАМИ

Для перевірки працездатності програми зробимо розрахунок оптимального шляху для графа, докладно розглянутого раніше (п.3.3), з вершини 1 в вершину ??laquo; 5 raquo ;.

Рис. 9

Повний хід виконання програми представлений на малюнку малюнку 10.

Рис. 10

Результати виконання наступні: вершини, через які шлях оптимальний від першої до п'ятої точки 1,3,6,5 послідовно. Загальна вартість шляху 20, що відповідає попереднім розрахункам.

Нижче представлено зміст текстового файлу dalg.txt, з результатами роботи програми:

=== Результати виконання завдання [test] === -

Матриця суміжності для поточного графа:

V1V1=0 V1V2=2 V1V3=4 V1V4=0

V2V1=2 V2V2=0 V2V3=1 V2V4=0

V3V1=4 V3V2=1 V3V3=0 V3V4=1

V4V1=0 V4V2=0 V4V3=1 V4V4=0

Початкова вершина: 1

Кінцева вершина: 4

Розрахунок шляху для завдання [test] завершений.

Вершини, шлях через які оптимальний: V1-V2-V3-V4

Довжина шляху: 4