Сутність теорії про знаходження найкоротших шляхів, оптимального маршруту за допомогою математичного об"єкту - графу. Розробка схем алгоритмів, рішення задач з використанням алгоритму Дейкстри та Флойда, матричного методу, модифікованих алгоритмів.
Аннотация к работе
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ КУРСОВА РОБОТА на тему: Розробка програмних продуктів на основі сучасних платформ програмування з дисципліни «Новітні платформи програмування»Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від перебування оптимального маршруту між двома обєктами на місцевості (наприклад, найкоротший шлях від будинку до університету), в системах автопілота, для знаходження оптимального маршруту при перевезеннях, комутації інформаційного пакету в Internet і т. д. При знаходженні оптимального маршруту при перевезеннях стоїть завдання своєчасно задовольняти потреби в перевезеннях, вдосконалювати організацію перевезень, забезпечити повне транспортне обслуговування, підвищувати якість і ефективність роботи, оновлювати структуру транспортних засобів, розвивати і вдосконалювати виробничо-технічну базу, впроваджувати прогресивні технології, підвищувати рівень безпеки перевезень, знижувати негативний вплив на навколишнє середовище, забезпечувати впровадження компютерних систем в організацію та управління рухом, проводити маркетингові дослідження з метою конкуренції на ринку транспортних послуг. Існують декілька найбільш ефективних алгоритмів знаходження найкоротшого шляху: · алгоритм Дейкстри (використовується для знаходження оптимального маршруту між двома вершинами);При рішенні багатьох практичних задач виникає необхідність представлення відносин між будь якими обєктами. Розглянемо задачу пошуку найкращого маршруту (шляху) на графі (у змісті найкоротшої відстані). Існує безліч типів задач про найкоротший шлях :між двома заданими вершинами; між заданою вершиною і всіма іншими; між кожною парою вершин у графі; між двома заданими вершинами для шляхів, що проходять через одну чи кілька зазначених вершин; перший, другий, третій і т.д. найкоротші шляхи в графі.Обєкти розглядаються як вершини, або вузли графу, а звязки - як дуги, або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість звязків і додатковими даними про вершини або ребра. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини - це статті, а дуги (орієнтовані ребра) - посилання на інші статті.Основним завданням даного курсового проекту є програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа. Програма повинна працювати так, щоб користувач за допомогою різних методів зміг вивести на екран найкоротший шлях між вершинами і їх довжину.В теорії графів, задача про найкоротший шлях полягає в знаходженні такого шляху між двома вершинами (або вузлами) графу, що сума ваг ребер з яких він складається мінімальна.Алгоритм голландського вченого Едсгер Дейкстри знаходить всі найкоротші шляхи з однієї заданої вершини графа до всіх інших. Мінусом даного методу є неможливість обробки графів, в яких є ребра з негативною вагою, тобто якщо, наприклад, деяка система передбачає збиткові для Вашої фірми маршрути, то для роботи з нею слід скористатися відмінним від алгоритму Дейкстри методом. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі), а масив позначок заповнюється нулями.Припустимо, що ми маємо позначений орграф, що містить час польоту по маршрутах, що звязує визначені міста, і ми хочемо побудувати таблицю, де приводився б мінімальний час перельоту з одного (довільного) міста в будь-який іншій. У цьому випадку ми зіштовхуємося з загальною задачею пошуку найкоротших шляхів, тобто перебуванням найкоротших шляхів між усіма парами вершин орграфа. Загальна задача перебування найкоротших шляхів полягає в пошуку для кожної упорядкованої пари вершин (v, w) будь-якого шляху від вершини v до вершини w, довжина якого мінімальна серед усіх можливих шляхів від v до w. Можна вирішити цю задачу, послідовно застосовуючи алгоритм Дейкстри для кожної вершини, що повідомляється як джерело. A[i, j] містить значення найменшої довжини шляху з вершини i у вершину j, що не проходять через вершини з номером, більшим ніж k.Елемент Sij , що стоїть на перетинанні i-го рядка й j-го стовпця, покладається рівним 1 при наявності прямого звязку (дуги Eij) між вершинами Vi й Vj і 0 - при відсутності такого звязку Далі визначається матриця S2 = S S за наступним правилом додавання елементів матриць S: При знаходженні матриці r-ї використовують такі ж операції: , елементи якої: Розрахунок матриці закінчується, якщо в процесі розрахунку матриці виконується рівністьМодифікація алгоритму полягає в тому, що на початковому етапі вибираються і запамятовуються , так звані , перші мінімальні початкові відправні точки (номери вузлів, що мають найкоротші відстані ) і другий початкові відправні точки (номери вузлів, відстань до яких наступне за величиною щодо першого мінімуму) .На цьому етапі нам потрібно знайти найкоротші шляхи чотирма способами. Рис.1. Натискаємо «Сформувати» і нам виводить матрицю по заданому графу.