Przejdź do treści
Wróć do wyników wyszukiwania

Algorytm Dijkstry

Autor metody
Edsger W. Dijkstra
Rok
1956
Typ
algorithm
Rodzina
Graph Algorithms

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Algorytm Dijkstry, wprowadzony przez Edsgera W. Dijkstrę w 1956 roku, jest jednym z fundamentalnych algorytmów w informatyce służącym do rozwiązywania problemu najkrótszej ścieżki z pojedynczego źródła.

Znajduje on najkrótszą ścieżkę od wierzchołka startowego do wszystkich pozostałych wierzchołków w grafie ważonym o nieujemnych wagach krawędzi.

Intuicja stojąca za metodą

Algorytm utrzymuje zbiór wierzchołków, dla których najkrótsze odległości od źródła są już znane, i iteracyjnie rozszerza ten zbiór, wybierając najbliższy nieprzetworzony wierzchołek i aktualizując odległości do jego sąsiadów. Kluczowym spostrzeżeniem jest własność zachłanności: gdy wierzchołek zostanie wybrany, jego odległość od źródła jest ostateczna, ponieważ wszystkie wagi krawędzi są nieujemne, więc każda dłuższa ścieżka przez nieodwiedzone wierzchołki nie może być krótsza. Gwarantuje to poprawność i optymalność.

Historia

Edsger W. Dijkstra opublikował swój algorytm w 1959 roku w trzystronicowym artykule, który stał się jednym z najczęściej cytowanych dzieł w informatyce. Algorytm wyłonił się z pracy Dijkstry nad komputerem ARMAC w Amsterdamie. Przez dziesięciolecia wprowadzono liczne ulepszenia, w tym lepsze struktury danych (kopce Fibonacciego osiągające złożoność O(E+VlogV)) i warianty dwukierunkowe. Algorytm pozostaje kluczowy dla nowoczesnych protokołów routingu, takich jak OSPF w sieciach komputerowych.

Kiedy stosować

Zastosuj algorytm Dijkstry przy znajdowaniu najkrótszych ścieżek w grafach o nieujemnych wagach krawędzi. Jest idealny dla systemów nawigacyjnych, routingu sieciowego i wszelkich problemów grafowych wymagających optymalnych ścieżek. Używaj go do znajdowania najkrótszych ścieżek z pojedynczego źródła do wszystkich wierzchołków. Dla grafów z ujemnymi wagami użyj algorytmu Bellmana-Forda. Dla wyszukiwania dwukierunkowego lub kierowanego heurystyką rozważ algorytm A*.

Ograniczenia i uwagi

  • Nie może obsługiwać grafów z ujemnymi wagami krawędzi
  • Oblicza najkrótsze ścieżki do wszystkich wierzchołków, nie tylko do jednego celu (choć może zakończyć się wcześniej)
  • Mniej wydajny niż A*, gdy dostępna jest informacja heurystyczna
  • Wymaga odkrycia wszystkich wierzchołków; nieefektywny dla bardzo rzadkiej łączności

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Prosty do zrozumienia i implementacji z jasnymi gwarancjami poprawności
  • Wydajny przy odpowiednich strukturach danych: O((V+E)logV) z kopcem binarnym, O(V²) z tablicą
  • Optymalny dla grafów o nieujemnych wagach; dowodzi optymalności obliczonych ścieżek
  • Działa zarówno na grafach skierowanych, jak i nieskierowanych
  • Podstawa dla licznych rozszerzeń i powiązanych algorytmów

Zastosowania

  • Systemy GPS i nawigacyjne: znajdowanie najkrótszych tras dla pojazdów i pieszych
  • Protokoły routingu sieciowego: określanie optymalnych ścieżek dla pakietów danych w sieciach komputerowych
  • Sieci społecznościowe: znajdowanie najkrótszych ścieżek połączeń między użytkownikami lub influencerami
  • Tworzenie gier: pathfinding dla sztucznej inteligencji i ruchu postaci niezależnych
  • Planowanie ruchu robotów: obliczanie optymalnych trajektorii dla systemów robotycznych
  • Telekomunikacja: optymalizacja routingu połączeń i ścieżek propagacji sygnału

Jak to działa

Jak to działa

1

Ustaw odległość źródła na zero, a wszystkie inne odległości na nieskończoność. Oznacz wszystkie wierzchołki jako nieodwiedzone i utwórz kolejkę priorytetową.

2

Wybierz nieodwiedzony wierzchołek o minimalnej odległości od źródła, korzystając z kolejki priorytetowej.

3

Dla każdego sąsiada wybranego wierzchołka, jeśli ścieżka przez wybrany wierzchołek oferuje krótszą odległość, zaktualizuj odległość sąsiada i dodaj go do kolejki priorytetowej.

Częste pułapki

  • Użycie algorytmu na grafach z ujemnymi wagami, co skutkuje nieprawidłowymi najkrótszymi ścieżkami
  • Nieefektywna implementacja z operacją extract-min o złożoności liniowej, prowadząca do słabej wydajności
  • Nieprawidłowe aktualizowanie odległości podczas ponownego odwiedzania sąsiadów różnymi ścieżkami

Najczęściej zadawane pytania

Dlaczego algorytm Dijkstry zawodzi na ujemnych wagach?

Algorytm zakłada, że po sfinalizowaniu wierzchołka nie można znaleźć krótszej ścieżki przez nieodwiedzone wierzchołki. Przy ujemnych wagach, dłuższa ścieżka może później zostać poprawiona przy użyciu ujemnej krawędzi, co narusza to założenie.

Jakiej struktury danych należy użyć do kolejki priorytetowej?

Kopce binarne zapewniają operacje O(logV) zarówno dla wstawiania, jak i ekstrakcji, co skutkuje całkowitą złożonością O((V+E)logV). Kopce Fibonacciego osiągają O(E+VlogV), ale mają duże stałe czynniki. Tablice dobrze sprawdzają się dla małych grafów.

Jak algorytm Dijkstry może znaleźć ścieżkę do jednego konkretnego celu?

Zakończ algorytm natychmiast po wybraniu wierzchołka docelowego (jego odległość jest sfinalizowana), unikając niepotrzebnych obliczeń. Alternatywnie, odtwórz ścieżkę, utrzymując wskaźniki rodzica podczas wykonania.

Czy algorytm Dijkstry można stosować w grafach nieskierowanych?

Tak, grafy nieskierowane można reprezentować jako grafy skierowane z krawędziami w obu kierunkach dla każdej krawędzi nieskierowanej, każda o tej samej wadze. Algorytm działa identycznie na reprezentacji dwukierunkowej.

Pokrewne metody

Źródła

  1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ISBN: 978-0-262-03384-8
    Skopiowano.