праведливо називають продовженням С і будь-яка працездатна програма мовою С буде підтримуватися компілятором С + +, при переході від С до С + + був зроблений досить істотний стрибок. Мова С + + вигравав від своєї спорідненості з мовою С протягом багатьох років, оскільки багато програмісти виявили, що для того, щоб повною мірою скористатися перевагами мови С + +, їм потрібно відмовитися від деяких своїх колишніх знань і придбати нові, а саме : вивчити новий спосіб концептуальності та вирішення проблем програмування. Перед тим як починати освоювати С + +, Страуструп і більшість інших програмістів, що використовують С + + вважають вивчення мови С необов'язковим. C + + в даний час вважається панівною мовою, використовуваним для розробки комерційних продуктів, 90% ігор пишуться на С + + з застосуванням DirectX. Проаналізувавши і порівнявши всі розглянуті мови програмування, для вирішення свого завдання мною був обраний Delphi 7., Т.к. для мене він є найбільш простим в обігу, має найбільш зрозумілий інтерфейс і простий синтаксис написання програм. [5]
1.3 Мета і завдання курсової роботи
Метою даної курсової роботи є розробка програми для знаходження всіх найкоротших шляхів в орієнтованому і неорієнтованому графах, використовуючи алгоритм Флойда.
Завдання курсової роботи: визначення вхідних даних; аналіз завдання і вибір методів її вирішення; розробка алгоритму для вирішення поставленого завдання; розробка програми на одній з мов високого рівня;
2. Аналіз завдання і методів її вирішення
2.1 Завдання пошуку виділеного найкоротшого шляху
Кожній дузі (x, y) вихідного графа G поставимо у відповідність число a (x, y). Якщо в графі G відсутня деяка дуга (x, y), покладемо a (x, y) =. Будемо називати число a (x, y) довжиною дуги (x, y), хоча a (x, y) можна також інтерпретувати як відповідні витрати або відповідний ваговий коефіцієнт. Визначимо довжину шляху як суму довжин окремих дуг, що складають цей шлях.
Для будь-яких двох вершин s і t графа G можуть існувати кілька шляхів, що з'єднують вершину s з вершиною t. Шлях, що має мінімально можливу довжину між називається найкоротшим шляхом між вершинами s і t.
Розглянемо актуальність даної задачі в реальному житті на прикладі.
Припустимо, що ви хочете проїхати з Бостона в Лос-Анджелес, використовуючи магістральні шосейні дороги, що з'єднують різні штати. Як вибрати найкоротший маршрут?
Побудуйте граф, вершини якого відповідають точкам з'єднання розглянутих доріг. Нехай кожна дуга графа відповідає шосейній дорозі, що з'єднують пункти, представлені відповідними вершинами. Нехай довжина шляху визначаться завдовжки (у кілометрах) відповідної ділянки дороги. Тепер завдання пошуку оптимального маршруту руху між Бостоном і Лос-Анджелесом може бути зведена до задачі відшукання в побудованому графі найкоротшого шляху між вершинами, відповідними Бостону, звідки ви починаєте подорож, і Лос-Анджелесу, де ваша подорож закінчується.
2.2 Алгоритм Дейкстри
Для знаходження найкоротшого шляху між двома конкретними вершинами s і t широко застосовується алгоритм Дейкстри. Далі розглянемо кроки даного алгоритму.
Крок 1. перед початком вик...
