Алгоритми пошуку найкоротшого шляху

9.1 Принципи роботи алгоритму Дейкстри

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

Кроки алгоритму:

1. Ініціалізація:

• Встановлюємо відстань до початкової вершини рівним 0.
• Встановлюємо відстань до всіх інших вершин рівним безкінечності.
• Створюємо множину неперевірених вершин.

2. Вибір поточної вершини:

• Обираємо неперевірену вершину з найменшою відстанню (початкова вершина на першому кроці).

3. Оновлення відстаней:

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

4. Позначаємо поточну вершину як перевірену:

• Видаляємо поточну вершину з множини неперевірених вершин.

5. Повторюємо кроки 2-4, поки не будуть перевірені всі вершини або не досягнемо цільової вершини.

Часова та простірна складність алгоритму Дейкстри:

Часова складність:

O((V + E) log V) при використанні черги з пріоритетом (наприклад, купа Фібоначчі), де V — кількість вершин, E — кількість ребер.

O(V^2) при використанні простого списку для зберігання відстаней.

Простірна складність:

O(V) для зберігання відстаней і предків (для відновлення шляху).

9.2 Реалізація алгоритму Дейкстри

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

Приклад реалізації алгоритму Дейкстри з використанням черги з пріоритетом (купа):

import heapq

def dijkstra(graph, start):
    # Ініціалізація
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    parents = {vertex: None for vertex in graph}
            
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
            
        # Якщо поточна відстань більша записаної, пропускаємо вершину
        if current_distance > distances[current_vertex]:
            continue
            
        # Оновлення відстаней до сусідніх вершин
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            # Якщо знайдено коротший шлях до сусідньої вершини
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parents[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
            
    return distances, parents
            
# Приклад використання:
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
start_vertex = 'A'
distances, parents = dijkstra(graph, start_vertex)
print("Найкоротші відстані від початкової вершини:", distances)
print("Предки для відновлення шляху:", parents)

Вивід:

Найкоротші відстані від початкової вершини: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Предки для відновлення шляху: {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}

9.3 Приклади задач, вирішуваних з використанням алгоритму Дейкстри

Класичні приклади задач, вирішуваних з використанням алгоритму Дейкстри:

1. Оптимізація маршрутів у транспортних мережах

Знаходження найкоротшого шляху між точками у транспортній мережі (наприклад, між містами).

Застосування:

Навігаційні системи, такі як Google Maps, використовують алгоритм Дейкстри для розрахунку оптимальних маршрутів.

2. Планування маршрутів доставки

Оптимізація маршрутів для служб доставки товарів, щоб мінімізувати витрати та час доставки.

Застосування:

Логістичні компанії використовують алгоритм Дейкстри для планування маршрутів доставки та зниження операційних витрат.

3. Управління мережами

Оптимізація маршрутизації пакетів даних у комп'ютерних мережах для мінімізації затримок та збільшення пропускної здатності.

Застосування:

Протоколи маршрутизації, такі як OSPF (Open Shortest Path First), використовують алгоритм Дейкстри для знаходження найкоротших шляхів у мережах.

4. Аналіз соціальних мереж

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

Застосування:

Соціальні платформи аналізують зв'язки між користувачами для надання рекомендацій та аналізу мережевої активності.

5. Ігри та віртуальні світи

Знаходження шляху для персонажів у ігрових світах з перешкодами та різними рівнями складності.

Застосування:

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

6. Системи управління енергією

Оптимізація розподілу енергії в електромережах для мінімізації втрат та забезпечення надійності постачань.

Застосування:

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

Приклад:

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

7. Системи евакуації та планування шляху

Оптимізація маршрутів евакуації у будівлях або містах для швидкого та безпечного виходу людей у разі надзвичайних ситуацій.

Застосування:

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

Приклад:

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