ЗМІСТ
ЗАВДАННЯ
Постановка завдання і сфера її застосування
Загальні відомості про графах
Алгоритм Дейкстри
Алгоритм, реалізований у програмі
ОСОБЛИВОСТІ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
ПРИКЛАД ВИКОРИСТАННЯ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
ВИСНОВОК
ЛІТЕРАТУРА
ЗАВДАННЯ
. Розробити алгоритм реалізації на ЕОМ процесу пошуку найкоротшого шляху в графі (методом Дейкстри). Передбачити перевірку допустимості ваг дуг графа.
. Написати й налагодити програму, що реалізовує розроблений алгоритм.
. Перевірити працездатність програми на тестових прикладах.
Постановка завдання і сфера її застосування
Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів останнім часом інтенсивно розвивається.
Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від знаходження оптимального маршруту між двома об'єктами на місцевості (наприклад, найкоротший шлях від дому до університету), в системах автопілота, для знаходження оптимального маршруту при перевезеннях , комутації інформаційного пакету в Internet і т.п.
Найкоротший шлях розглядається за допомогою деякого математичного об'єкта, званого графом.
Існують три найбільш ефективних алгоритму знаходження найкоротшого шляху:
· алгоритм Дейкстри (використовується для знаходження оптимального маршруту між двома вершинами);
· алгоритм Флойда;
· алгоритм Йена.
Основним завданням даної курсової роботи є програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа.
Програма повинна працювати так, щоб користувач вводив кількість вершин і довжини ребер графа, а після обробки цих даних на екран виводився найкоротший шлях між двома заданими вершинами і його довжина. Необхідно передбачити різні результати пошуку, щоб програма не видавала помилок і працювала правильно. Дана програма може використовуватися в дискретної математики для дослідження графів або в якості наочного посібника, що демонструє застосування алгоритму Дейкстри на практиці.
Загальні відомості про графах
алгоритм граф шлях працездатність
Граф G (рис.1.1) задається множиною точок (вершин) х 1, х 2, ..., х n. (Яке позначається через Х) і безліччю ліній (ребер) а 1, а 2, ..., а m. (Яке позначається символом А), що з'єднують між собою всі або частину цих точок. Таким чином, граф G повністю задається (і позначається) парою (Х, А). Якщо ребра з безлічі А орієнтовані, що зазвичай показується стрілкою, то вони називаються дугами, і граф з такими ребрами називається орієнтованим графом.
Наприклад, якщо дорога має не двох-, а односторонній рух то напрямок цього руху буде показано стрілкою.
Якщо ребра не мають орієнтації, то граф називається неорієнтованим, (двосторонній рух).
В орієнтованому графі дуга позначається впорядкованої парою, що складається з початкової та кінцевої вершин, її напрямок передбачається заданим від першої вершини до другої.
