Grafy. Znajdowanie najkrótszej drogi

0
0
0

1. Co to jest graf?

Graf to struktura danych używana do przedstawiania połączeń między różnymi obiektami.

Graf składa się z:

  • wierzchołków – np. miasta, komputery, osoby

  • krawędzi – połączenia między nimi (np. drogi)

Przykład grafu:

Liczby oznaczają koszt przejścia (np. długość drogi).

Jednym z najczęstszych problemów jest znalezienie najkrótszej drogi między dwoma wierzchołkami.

2. Reprezentacja grafu w Pythonie

Graf można zapisać w Pythonie na kilka sposobów. Jednym z najprostszych jest słownik (dictionary).

Przykład grafu:

Interpretacja:

  • z A do B koszt wynosi 5

  • z A do C koszt wynosi 2

3. Problem najkrótszej drogi

Załóżmy, że chcemy znaleźć najkrótszą drogę z A do D.

Możliwe trasy:

  1. A → B → D
    koszt = 5 + 3 = 8

  2. A → C → D
    koszt = 2 + 4 = 6

Najkrótsza droga to:

A → C → D (koszt 6)

Do rozwiązywania takich problemów często stosuje się algorytm Dijkstry.

4. Algorytm Dijkstry – idea działania

Algorytm działa według następujących kroków:

  1. Nadajemy wierzchołkowi startowemu koszt 0.

  2. Wszystkim pozostałym przypisujemy nieskończoność.

  3. Wybieramy wierzchołek o najmniejszym koszcie.

  4. Sprawdzamy jego sąsiadów i aktualizujemy ich koszty.

  5. Powtarzamy aż odwiedzimy wszystkie wierzchołki.

Schemat blokowy algorytmu Dijkstry:

5. Przykład algorytmu w Pythonie

Poniższy program oblicza najkrótsze odległości od punktu A do wszystkich innych punktów.

Kod jest celowo napisany prosto – bez funkcji, aby był łatwiejszy do zrozumienia.

6. Zastosowania grafów

Algorytmy znajdowania najkrótszej drogi są wykorzystywane w wielu systemach:

Nawigacja GPS

Programy takie jak Google Maps obliczają najkrótszą lub najszybszą trasę.

Internet

Routery obliczają najlepszą drogę przesyłania pakietów danych.

Gry komputerowe

Postacie w grach obliczają najkrótszą drogę do celu.

Transport i logistyka

Firmy optymalizują trasy dostaw.

7. Podsumowanie

Grafy są jedną z najważniejszych struktur danych w informatyce. Pozwalają modelować różnego rodzaju sieci i połączenia.

Najważniejsze informacje:

  • graf składa się z wierzchołków i krawędzi

  • może przedstawiać np. sieć dróg

  • do znajdowania najkrótszej drogi stosuje się algorytm Dijkstry

  • Python pozwala łatwo implementować grafy przy użyciu słowników

Znajomość grafów jest bardzo ważna w takich dziedzinach jak:

  • sztuczna inteligencja

  • sieci komputerowe

  • analiza danych

  • systemy nawigacyjne

Was this helpful?

0 / 0

Post Views: 46