Зміст
Введення
1. Аналіз предметної області
1.1 Основні визначення
1.2 Комп'ютерні засоби для реалізації завдання
1.3 Мета і завдання курсової роботи
2. Аналіз завдання і методів її вирішення
2.1 Завдання пошуку виділеного найкоротшого шляху
2.2 Алгоритм Дейкстри
2.3 Завдання пошуку всіх найкоротших шляхів
2.4 Алгоритм Флойда
3. Розробка програми
3.1 Характеристика програми і системні вимоги
3.2 Опис модульної структури розробленої програми
3.3 Опис діалогу з користувачем
3.4 Контрольний приклад
Висновок
Список літератури
Введення
У цій роботі я розглянув рішення однієї з найважливіших задач дискретної математики - знаходження найкоротшого шляху між парами всіх вершин в орієнтованому і неорієнтованому графах, шляхом використання алгоритму Флойда.
При вирішенні даної задачі графічними методами можуть виникнути складнощі, пов'язані з важким візуальним сприйняттям графа, у зв'язку з цим свою актуальності набуває знаходження шляхів, за допомогою алгоритму Флойда.
Важливість даної курсової роботи полягає в тому, що вищеописана проблема дозволяється за допомогою розробленої в ході виконання даного проекту, програми.
Курсова робота носить навчальний характер. У ході її виконання реалізуються наявні знання з курсу дискретної математики за рішенням завдання в програмній інтерпретації на мові програмування Deplhi 7.0, формуються навички з визначення вхідних-вихідних даних, аналіз предметної області, вибір методів і засобів для вирішення поставленого завдання. Також купуються навички з розробки алгоритму по рішення задачі. А знання комп'ютера і наявність досвіду в програмуванні в наш час особливо вітається у сфері інформаційних технологій.
1. Аналіз предметної області
1.1 Основні визначення
Графом G=(X, U) будемо називати сукупність двох кінцевих множин; безлічі вершин X={x, ... x} і безлічі ребер (дуг) U={u .... u}, що складається з деяких пар елементів (x, x) множини X. Геометрично граф може бути представлений у вигляді малюнка, в якому вершинам відповідають точки, а ребрам лінії, що з'єднують всі або деякі з цих точок. Граф називається поміченим, якщо його вершин приписані деякі мітки, наприклад номера.
Якщо пари вершин (x, x) в безлічі U є невпорядкованими (тобто, порядок з'єднання вершин неістотний), то граф називається неорієнтованим (неорграфом), а пари (x, x) - ребрами цього графа (малюнок 1 ).
Малюнок 1
дискретна математика орієнтований граф
При цьому вершини x, x називають кінцями (кінцевими вершинами) ребра. У даному випадку також кажуть, що ребро (x, x) - з'єднує вершини xі x.
Якщо пари вершин (x, x) в безлічі U є впорядкованими (тобто, порядок з'єднання вершин существенен), то граф називається орієнтованим (орграфом), а пари (x, x) - дугами (малюнок 2).
Малюнок 2
При...
