Motywacja

Dijkstra rozbudowuje zbiór wierzchołków, których najkrótsza odległość jest już znana. Zawsze zatwierdza wierzchołek o najmniejszej odległości, który nie został jeszcze zatwierdzony, a następnie wykorzystuje go do poprawienia (relaksacji) odległości do jego sąsiadów.

Dlaczego warto poznać algorytm Dijkstry?

• Wszechstronne zastosowanie: wyznaczanie tras GPS, routing pakietów sieciowych i dowolne wyszukiwanie ścieżek o najniższym koszcie.
• Skuteczne podejście zachłanne: przejrzysty przykład wyboru zachłannego, który gwarantuje optymalne rozwiązanie, o ile wagi są nieujemne.
• Podstawa: idea relaksacji pojawia się ponownie w algorytmie A* i innych algorytmach wyznaczania najkrótszych ścieżek.

Ważne: algorytm Dijkstry zakłada, że nie ma ujemnych wag. W przypadku ujemnych krawędzi potrzebny jest algorytm Bellmana-Forda, który poznasz na następnym kursie.