Algorytmy wyszukiwania najkrótszej ścieżki

9.1 Zasady działania algorytmu Dijkstry

Algorytm Dijkstry to algorytm do znajdowania najkrótszych ścieżek od początkowego wierzchołka do pozostałych wierzchołków w grafie z nieujemnymi wagami krawędzi. Algorytm wykorzystuje podejście zachłanne, wybierając na każdym kroku wierzchołek o najmniejszej znanej odległości od początkowego wierzchołka i aktualizując odległości do sąsiadujących wierzchołków.

Kroki algorytmu:

1. Inicjalizacja:

• Ustawiamy odległość do początkowego wierzchołka równą 0.
• Ustawiamy odległość do wszystkich pozostałych wierzchołków równą nieskończoności.
• Tworzymy zbiór nieodwiedzonych wierzchołków.

2. Wybór bieżącego wierzchołka:

• Wybieramy nieodwiedzony wierzchołek o najmniejszej odległości (początkowy wierzchołek na pierwszym kroku).

3. Aktualizacja odległości:

• Dla każdego sąsiadującego wierzchołka bieżącego wierzchołka, jeśli nowa ścieżka przez bieżący wierzchołek jest krótsza od znanej ścieżki, aktualizujemy odległość do tego wierzchołka.

4. Oznaczamy bieżący wierzchołek jako odwiedzony:

• Usuwamy bieżący wierzchołek ze zbioru nieodwiedzonych wierzchołków.

5. Powtarzamy kroki 2-4, aż wszystkie wierzchołki zostaną odwiedzone lub dojdziemy do wierzchołka docelowego.

Skomplikowanie czasowe i pamięciowe algorytmu Dijkstry:

Skomplikowanie czasowe:

O((V + E) log V) przy użyciu kolejki priorytetowej (np. kopiec Fibonacciego), gdzie V — liczba wierzchołków, E — liczba krawędzi.

O(V^2) przy użyciu prostego listy do przechowywania odległości.

Skomplikowanie pamięciowe:

O(V) do przechowywania odległości i przodków (do odtworzenia ścieżki).

9.2 Implementacja algorytmu Dijkstry

Implementacja algorytmu Dijkstry jest długa, ale bardzo prosta. Polecam spróbować ją zrozumieć. Jeśli coś będzie niejasne — wróć nieco wyżej i przeczytaj jeszcze raz główne kroki algorytmu.

Przykład implementacji algorytmu Dijkstry przy użyciu kolejki priorytetowej (kopiec):

import heapq

def dijkstra(graph, start):
    # Inicjalizacja
    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)
            
        # Jeśli bieżąca odległość jest większa niż zapisana, pomijamy wierzchołek
        if current_distance > distances[current_vertex]:
            continue
            
        # Aktualizacja odległości do sąsiadujących wierzchołków
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            # Jeśli znaleziono krótszą ścieżkę do sąsiedniego wierzchołka
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parents[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
            
    return distances, parents
            
# Przykład użycia:
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("Najkrótsze odległości od początkowego wierzchołka:", distances)
print("Przodkowie do odtworzenia ścieżki:", parents)

Wynik:

Najkrótsze odległości od początkowego wierzchołka: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Przodkowie do odtworzenia ścieżki: {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}

9.3 Przykłady zadań rozwiązywanych z użyciem algorytmu Dijkstry

Klasyczne przykłady zadań rozwiązywanych z użyciem algorytmu Dijkstry:

1. Optymalizacja tras w sieciach transportowych

Znajdowanie najkrótszej ścieżki pomiędzy punktami w sieci transportowej (np. między miastami).

Zastosowanie:

Systemy nawigacyjne, takie jak Google Maps, wykorzystują algorytm Dijkstry do obliczania optymalnych tras.

2. Planowanie tras dostaw

Optymalizacja tras dla usług dostawczych, aby zminimalizować koszty i czas dostawy.

Zastosowanie:

Firmy logistyczne używają algorytmu Dijkstry do planowania tras dostaw i obniżenia kosztów operacyjnych.

3. Zarządzanie sieciami

Optymalizacja routingu pakietów danych w sieciach komputerowych dla minimalizacji opóźnień i zwiększenia przepustowości.

Zastosowanie:

Protokoły routingu, takie jak OSPF (Open Shortest Path First), używają algorytmu Dijkstry do znalezienia najkrótszych ścieżek w sieciach.

4. Analiza sieci społecznościowych

Znajdowanie najkrótszych ścieżek i mierzenie centralności w grafach społecznościowych (np. do znalezienia najbardziej wpływowych użytkowników).

Zastosowanie:

Platformy społecznościowe analizują połączenia między użytkownikami dla oferowania rekomendacji i analizy aktywności sieciowej.

5. Gry i wirtualne światy

Znajdowanie ścieżki dla postaci w światach gier z przeszkodami i różnymi poziomami trudności.

Zastosowanie:

Silniki gier używają algorytmu Dijkstry do obliczania ruchu postaci i obiektów w wirtualnych światach.

6. Systemy zarządzania energią

Optymalizacja dystrybucji energii w sieciach elektrycznych dla minimalizacji strat i zapewnienia niezawodności dostaw.

Zastosowanie:

Firmy elektroenergetyczne używają algorytmu Dijkstry do optymalizacji tras przesyłu energii w sieciach, aby zminimalizować straty energii i unikać przeciążeń.

Przykład:

W sieciach elektrycznych każdy węzeł przedstawia podstację, a krawędzie — linie przesyłowe o różnych poziomach oporu. Algorytm Dijkstry pomaga znaleźć ścieżkę z najmniejszym oporem od źródła energii do odbiorcy.

7. Systemy ewakuacji i planowania trasy

Optymalizacja tras ewakuacyjnych w budynkach lub miastach dla szybkiego i bezpiecznego wyprowadzenia ludzi w przypadku sytuacji nadzwyczajnych.

Zastosowanie:

Architekci i inżynierowie używają algorytmu Dijkstry do planowania tras ewakuacyjnych, aby zapewnić bezpieczne i szybkie usunięcie ludzi z niebezpiecznych stref.

Przykład:

W budynku mieszkalnym lub biurowym węzły grafu przedstawiają pokoje i korytarze, a krawędzie — ścieżki między nimi. Algorytm Dijkstry może być używany do znalezienia najkrótszej ścieżki od dowolnego punktu w budynku do najbliższego wyjścia.