ЗМІСТ
Введення
.Загальні відомості про графах
2.Постановка завдання
.Алгорітм Дейкстри
.Алгорітм Беллмана-Форда
.Алгорітм А *
.Практіческое застосування
Висновок
Список використаної літератури
Програми
ВСТУП
«Завдання пошуку найкоротшого шляху» (задача про мінімальний шлях, задача про диліжансі), останнім часом набула широкого поширення, завдяки своєму застосуванню для вирішення безлічі інших завдань.
В даний час вона застосовується в алгоритмах пошуку оптимального шляху між двома об'єктами (GPS-навігація), в системах автоматичного пілотування, для знаходження найкоротшого шляху проходження Internet-пакета по мережі, і безлічі інших.
Завдання про найкоротший шлях є однією з найважливіших класичних задач теорії графів. На сьогоднішній день відомо безліч алгоритмів для її вирішення.
Найкоротший шлях розглядається за допомогою математичної моделі, званої графом.
1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО графа
алгоритм завдання шлях граф
Як вже було сказано, граф - це математична модель, представлена ??сукупністю безлічі вершин і зв'язків між ними.
ВИДИ ГРАФІВ І МЕТОДИ ЇХ ЗАВДАННЯ
Кожна пара вершин, що мають зв'язок, називається ребром графа. Ребра, що мають напрямки, називаються орієнтованими. У зв'язку з наявністю/відсутністю орієнтованих ребер в графі, графи поділяються на:
· Орієнтовані графи- містять тільки орієнтовані ребра;
· Неорієнтовані графи-містять тільки неорієнтовані ребра;
· Змішані графи - містять як орієнтовані ребра, так і неорієнтовані.
Ребро і вершина, якій воно належить вважаються інцидентними.
Подграф вихідного графа - це граф, що містить якесь підмножина вершин даного графа і якесь підмножина інцидентних їм рёбер.Граф з p вершинами і q ребрами називається (p, q) -графом. Зазвичай граф представляється за допомогою подібної діаграми:
Орієнтований граф, з 6-ма вершинами
Дана діаграма наочно відображає наявні вершини, і зв'язки між ними, проте для вирішення деяких завдань пріменяютсяі інші способи завдання графа:
Матриця суміжності
Матриця суміжності графа G (V, E), де V-безліч вершин, E- безліч ребер даного графа це квадратна матриця A розміру n, в якій значення елемента aij дорівнює числу ребер з i-й вершини графа в j-ю вершину.
Матриця суміжності виглядає наступним чином:
Матриця суміжності
Граф, відповідний даній матриці
Матриця інцидентності
Матриця інцидентності - форма представлення графа, в якій зазначаються зв'язку між інцидентними елементами графа (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки - вершин. Ненульове значення в осередку матриці вказує зв'язок між вершиною і ребром (їх инцидентность). Приклад матриці інцидентності:
Матриця інцидентності
Граф, відповідний даній матриці
Також існують інші способи, але наведені є найбільш ємними і популярними.
МАРШРУТИ, ШЛЯХИ, зв'язності
Маршрут в графі - це чередующаяся послідовність вершин і ребер, в якій будь-які два сусідні елементи інцідентни. Якщо початкова та кінцева вершини маршруту збігаються, то маршрут замкнутий, інакше відкритий. Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо також різні і вершини.
Шлях це така послідовність ребер в графі, що кінець одного ребра є початком іншого. Шлях можна вважати окремим випадком маршруту.
Зв'язність - це одне з найбільш простих властивостей, яким може володіти граф.
Граф називається зв'язковим, якщо будь-яка пара його вершин з'єднана простий ланцюгом. Максимальний зв'язний підграф графа G називається компонентом зв'язності, або просто компонентою графа G. Таким чином, незв'язних граф має щонайменше 2 компоненти.
Зв'язний граф
На малюнку 4 наведено приклад зв'язного графа, з простими ланцюгами, що з'єднують всі вершини графа. Так, в даному графі вершини AИ Bсоедінени простий ланцюгом {A, B}, вершини B иd простий ланцюгами {B, E, D}, {B, C, D}, {B, A, D}.
Найпростішим прикладом незв'язного графа є граф з ізолірованнойвершін...
