Інформатика – Поглиблений рівень

Прочитайте!

З однієї станції метро можна потрапити до іншої станції різними шляхами. Наведіть приклад пошуку найкоротшого шляху у відомому вам метро. У процесі пошуку найкоротшого шляху у графі між двома
вершинами відшукується шлях, для якого сума ваг його ребер є мінімальною серед усіх інших шляхів. Така задача може виконуватися для неорієнтованого й орієнтованого графів.

Задача пошуку найкоротшого шляху у графі має важливе практичне значення. Наприклад, у GPS-навігаторах здійснюється пошук найкоротшого шляху між двома об’єктами. Перехрестя вулиць є аналогом вершин, а вулиці (дороги) з їхніми довжинами — ребрами. Якщо сума довжин доріг між об’єктами мінімальна, то вважається, що знайдено найкоротший шлях.

Якщо вага ребер не вказана, то найкоротшим шляхом вважається той, що містить найменшу кількість ребер. На графі, зображеному на рис. 8.19, найкоротшим шляхом із вершини 3 у вершину 6 є шлях 3–4–5–6, сума ваг ребер якого дорівнює 9.

• Є різні варіанти задач про найкоротший шлях у графі:
  пошук найкоротшого шляху в задану вершину з усіх інших вершин графу;
• пошук найкоротшого шляху між двома заданими вершинами;
• пошук найкоротшого шляху з кожної вершини в усі інші вершини графу;
• пошук найкоротшого шляху, який проходить через задану множину вершин, та ін.

Нині для кожного типу задач пошуку найкоротшого шляху розроблено значну кількість алгоритмів. Розглянемо два з них: алгоритм Дейкстри й алгоритм Флойда — Уоршелла.

Алгоритм Дейкстри

Кур’єр доставляє кореспонденцію абонентам, користуючись схемою руху міського транспорту. Він майже щоденно відшукує найкоротший шлях від станції отримання кореспонденції до решти абонентів. Як він це робить? За допомогою алгоритму Дейкстри здійснюється пошук найкоротшого шляху від однієї вершини графу (стартової) до всіх його інших вершин.

Для полегшення опису алгоритму Дейкстри будемо називати вершину відвідуваною, якщо вона вже була включена будь-який шлях і її не можна більше включати в новий шлях, а вершину, яка ще не використовувалася на шляху і яка є суміжною з поточною, — видимою.

Наприклад, якщо вершина 0 (рис. 8.20) вже була включена в маршрут, то вона є відвідуваною, а якщо вершина 2 не включена в маршрут, то для неї видимими є вершини 3, 4 і 5. Ви знаєте, що вершини графу можуть позначатися різними ідентифікаторами. Але якщо передбачається реалізувати алгоритм мовою Python, то доцільніше вершини позначати цілими числами в діапазоні від 0 до n −1. У цьому випадку можна використовувати номери вершин як індекси. Сутність алгоритму Дейкстри така.

На прикладі графу, зображеного на рис. 8.20, за допомогою алгоритму Дейкстри знайдемо мінімальні відстані від вершини 0 до всіх інших вершин цього графу.

Загальний вигляд алгоритму Дейкстри можна подати так.

Для реалізації алгоритму Дейкстри мовою Python зважений неорієнтований граф можна реалізувати словником суміжності. У такому разі як ключ можна вибрати номер вершини, як значення — вагу ребра.

Завдання для самостійного виконання

Завдання 1. Для графу на рис. 8.19 визначте найкоротші шляхи від вершини 2 до всіх інших.

Завдання 2. Для графу на рис. 8.19 визначте найкоротші шляхи від кожної вершини до всіх інших.