ой. Вершина називається ізольованою, якщо вона не має інцидентних їй ребер. Приклад такого графа, з ізольованою вершиною D наведено на рис. 5:
ВЕС І ДОВЖИНА ШЛЯХИ
У деяких завданнях, ребрам ставлять у відповідність числа, (що позначаються ai - gt; ci) які називаютвесом (довжиною) ребра.
Тоді граф G можна описати як 3 безлічі:
X- безліч вершин, A - множина дуг, C - безліч ваг.
X={x1, x2, x3 ... xi}={a1, a2, a3 ... ai,}={c1, c2, c3 ... ci,}
Незв'язний граф
Зважений граф
З малюнка видно, що вага ребра (4,5) дорівнює 15. Вага колії приймається рівним сумі ваг входять до нього ребер. Вага шляху A=(2,4,5), в даному випадку дорівнює сумі ваг ребер (2,4) і (4,5)=12 + 15=27.
2. ПОСТАНОВКА ЗАВДАННЯ
Завдання пошуку найкоротшого шляху це завдання, в якій необхідно знайти найкоротший шлях між двома точками (вершинами), на графі, зменшуючи суму ваг ребер, що складають цей шлях.
Ця задача може бути визначена і вирішена для орієнтованого, неорієнтованого та змішаного графів. Неорієнтовані граф в даному випадку представляє найлегшу задачу, без врахування напрямків ребер, в орієнтованому і змішаному графах, напрямок необхідно враховувати.
Існують різні постановки задачі про найкоротший шлях:
· Завдання про найкоротший шлях в заданий пункт призначення. Потрібно знайти найкоротший шлях в задану вершину призначення t, який починається в кожній з вершин графа (крім t). Помінявши напрямок кожного належить графу ребра, це завдання можна звести до задачі про єдиної вихідної вершині (в якій здійснюється пошук найкоротшого шляху з заданої вершини в усі інші).
· Завдання про найкоротший шлях між заданою парою вершин. Потрібно знайти найкоротший шлях із заданої вершини u в задану вершину v.
· Завдання про найкоротший шлях між усіма парами вершин. Потрібно знайти найкоротший шлях з кожної вершини u в кожну вершину v. Цю задачу теж можна розв'язати за допомогою алгоритму, призначеного для вирішення задачі про однієї вихідної вершині, проте зазвичай вона вирішується швидше.
Вага ребра також може замінюватися на вартість, швидкість, витрати і.т.п., залежно від конкретного завдання.
3. Алгоритм Дейкстри
Знаходить найкоротша відстань від однієї з вершин графа до всіх інших, працює тільки для графів без ребер негативного ваги.
ЗАВДАННЯ
Дан зважений орієнтований граф G (V, E) без петель і дуг негативного ваги. Знайти найкоротші шляхи від деякої вершини a графа G до всіх інших вершин цього графа.
АЛГОРИТМ
. Кожній вершині з V зіставимо мітку - мінімальне відоме відстань від цієї вершини до a. Алгоритм працює покроково - на кожному кроці він «відвідує» одну вершину і намагається зменшувати мітки. Робота алгоритму завершується, коли всі вершини відвідані.
. Ініціалізація. Мітка самої вершини a покладається рівною 0, мітки інших вершин - нескінченності. Це відображає те, що відстані від a до інших вершин поки невідомі. Всі вершини графа позначаються що не відвідані.
. Крок алгоритму. Якщо всі вершини відвідані, алгоритм завершується. В іншому випадку, з ще не відвіданих вершин вибирається вершина u, що має мінімальну мітку. Ми розглядаємо всілякі маршрути, в яких u є передостаннім пунктом. Вершини, в які ведуть ребра з u, назвемо сусідами цієї вершини. Для кожного сусіда вершини u, крім зазначених як відвідані, розглянемо нову довжину шляху, що дорівнює сумі значень поточної мітки u і довжини ребра, що з'єднує u з цим сусідом. Якщо отримане значення довжини менше значення мітки сусіда, замінимо значення мітки отриманим значенням довжини. Розглянувши всіх сусідів, пометим вершину u як відвідану і повторимо крок алгоритму
ПРИКЛАД
Як приклад візьмемо неорієнтовані граф, і знайдемо мінімальні відстані від першої вершини до всіх інших:
При ініціалізації алгоритму, мітка шуканої вершини позначається 0, мітки інших вершин - нескінченністю:
Крок №1: мінімальну мітку має вершина 1, її сусідами є 6, 3, 2. Розглянемо їх. Перший по черзі сусід вершини 1 - вершина 2, тому що довжина шляху до неї мінімальна. Довжина шляху в неї через вершину 1 дорівнює сумі найкоротшої відстані до вершини 1, значенням її мітки, і довжини ребра, що йде з 1-й в 2-ю, тобто 0 + 7=7. Це менше поточної мітки вершини 2, нескінченності, тому нова мітка...
