Algorytm Dijkstry znajduje najkrótsze ścieżki z jednego wierzchołka grafu do wszystkich pozostałych, pod warunkiem że żadna krawędź nie ma ujemnej wagi. Na małej mapie sześciu polskich miast z umownymi odległościami wyznacza w sześciu krokach trasę z Warszawy do Krakowa przez Łódź i Katowice: 38 jednostek zamiast 40 drogą bezpośrednią. Pokazujemy każdy krok w tabeli, kod w Pythonie z modułem heapq i w C++ z std::priority_queue, odtwarzanie trasy i przykład, w którym jedna ujemna waga daje zły wynik.
Na czym polega algorytm Dijkstry
Algorytm Dijkstry działa na grafie, czyli zbiorze wierzchołków (tu miast) połączonych krawędziami z wagami (tu odległościami). Na starcie zna tylko odległość do punktu wyjścia, równą zero. Do wszystkich innych wierzchołków przyjmuje nieskończoność.
W każdym kroku robi trzy rzeczy:
- Wybiera nieodwiedzony wierzchołek o najmniejszej znanej odległości.
- Uznaje tę odległość za ostateczną i oznacza wierzchołek jako odwiedzony.
- Sprawdza jego sąsiadów: jeśli droga przez wybrany wierzchołek jest krótsza od dotychczas znanej, zapisuje nową odległość i poprzednika.
Trzeci krok nazywa się relaksacją krawędzi. Poprzednik to miasto, z którego przyszła najlepsza znana droga, i dzięki niemu da się potem odtworzyć całą trasę. Algorytm kończy pracę, gdy odwiedzi wszystkie osiągalne wierzchołki.
Działa to dlatego, że wagi nie są ujemne. Jeśli wierzchołek ma najmniejszą odległość spośród nieodwiedzonych, żadna okrężna droga przez inne nieodwiedzone miasto nie może być krótsza: każda kolejna krawędź tylko dodaje. Z tego samego powodu przy ujemnych wagach algorytm traci gwarancję poprawnego wyniku, co pokazujemy niżej w kodzie.
Skąd się wziął: 64 miasta i 20 minut
Edsger W. Dijkstra, holenderski informatyk, opublikował algorytm w 1959 roku w czasopiśmie Numerische Mathematik, w trzystronicowej notatce “A note on two problems in connexion with graphs”. Okoliczności opisał sam w wywiadzie dla Communications of the ACM, opublikowanym w 2010 roku. Według jego wspomnień w 1956 roku potrzebował pokazu na uroczyste otwarcie komputera ARMAC w Amsterdamie. Zadanie miało być zrozumiałe dla osób spoza matematyki.
Wybrał najkrótszą drogę między dwoma miastami Holandii na uproszczonej mapie z 64 miastami. Liczba 64 nie była przypadkowa, bo do zapisania numeru miasta wystarczało wtedy sześć bitów. Pytanie brzmiało: jak najkrócej dojechać z Rotterdamu do Groningen? Dijkstra wspominał, że sam algorytm wymyślił w około 20 minut na tarasie kawiarni, bez ołówka i papieru. Po latach zobaczył, że korzystają z niego nawigacje samochodowe.
Na zdjęciu otwierającym tekst jest Edsger W. Dijkstra w 2002 roku. Fot. Hamilton Richards, Wikimedia Commons, licencja CC BY-SA 3.0.
Przykład: najkrótsza trasa z Warszawy
Nasz graf ma sześć miast i dziewięć dwukierunkowych połączeń. Wagi są umowne: przypominają proporcje odległości drogowych, ale nie są kilometrami z żadnej tabeli. Przyjęliśmy je tak, żeby w przykładzie było widać poprawianie odległości w trakcie działania algorytmu.
| Połączenie | Waga | Połączenie | Waga |
|---|---|---|---|
| Warszawa – Łódź | 13 | Łódź – Wrocław | 22 |
| Warszawa – Poznań | 30 | Łódź – Katowice | 18 |
| Warszawa – Kraków | 40 | Poznań – Wrocław | 18 |
| Łódź – Poznań | 21 | Wrocław – Katowice | 19 |
| Katowice – Kraków | 7 |

Krok po kroku: tabela odległości i poprzedników
Tabela pokazuje stan po każdym kroku dla startu w Warszawie. W nawiasie jest poprzednik, a ∞ oznacza miasto jeszcze nieosiągnięte. Pogrubiona wartość to odległość, która w danym kroku stała się ostateczna.
| Krok | Odwiedzany wierzchołek | Łódź | Poznań | Wrocław | Katowice | Kraków |
|---|---|---|---|---|---|---|
| 1 | Warszawa (0) | 13 (Warszawa) | 30 (Warszawa) | ∞ | ∞ | 40 (Warszawa) |
| 2 | Łódź (13) | 13 (Warszawa) | 30 (Warszawa) | 35 (Łódź) | 31 (Łódź) | 40 (Warszawa) |
| 3 | Poznań (30) | 13 | 30 (Warszawa) | 35 (Łódź) | 31 (Łódź) | 40 (Warszawa) |
| 4 | Katowice (31) | 13 | 30 | 35 (Łódź) | 31 (Łódź) | 38 (Katowice) |
| 5 | Wrocław (35) | 13 | 30 | 35 (Łódź) | 31 | 38 (Katowice) |
| 6 | Kraków (38) | 13 | 30 | 35 | 31 | 38 (Katowice) |
Najciekawszy jest krok 4. Po pierwszym kroku Kraków ma odległość 40, bo z Warszawy prowadzi tam bezpośrednia krawędź. Dopiero gdy algorytm odwiedza Katowice, okazuje się, że droga Warszawa – Łódź – Katowice – Kraków kosztuje 13 + 18 + 7 = 38. Odległość spada, a poprzednikiem Krakowa zostają Katowice.
W kroku 3 widać sytuację odwrotną. Przez Łódź do Poznania jest 13 + 21 = 34, czyli więcej niż 30 drogą bezpośrednią, więc wartość się nie zmienia. Wrocław dostaje 35 przez Łódź, a droga przez Poznań (30 + 18 = 48) też przegrywa.
Algorytm Dijkstry w Pythonie (heapq)
W Pythonie najprościej użyć modułu heapq. Dokumentacja Pythona opisuje go jako implementację kolejki priorytetowej na kopcu minimalnym: element o najmniejszej wartości jest zawsze na początku listy. Kopiec to drzewo, w którym każdy rodzic jest nie większy od swoich dzieci. Więcej o tej i innych strukturach piszemy w tekście o strukturach danych i ich zastosowaniach.
import heapq
def dijkstra(graf, start):
odleglosc = {w: float("inf") for w in graf}
poprzednik = {w: None for w in graf}
odleglosc[start] = 0
kolejka = [(0, start)]
odwiedzone = set()
while kolejka:
d, w = heapq.heappop(kolejka)
if w in odwiedzone:
continue # nieaktualny wpis w kolejce
odwiedzone.add(w)
for sasiad, waga in graf[w]:
if sasiad in odwiedzone:
continue # odległość sąsiada jest już ostateczna
nowa = d + waga
if nowa < odleglosc[sasiad]:
odleglosc[sasiad] = nowa
poprzednik[sasiad] = w
heapq.heappush(kolejka, (nowa, sasiad))
return odleglosc, poprzednik
def sciezka(poprzednik, cel):
wynik = []
while cel is not None:
wynik.append(cel)
cel = poprzednik[cel]
return wynik[::-1]
def graf_nieskierowany(krawedzie):
graf = {}
for a, b, waga in krawedzie:
graf.setdefault(a, []).append((b, waga))
graf.setdefault(b, []).append((a, waga))
return graf
krawedzie = [
("Warszawa", "Łódź", 13), ("Warszawa", "Poznań", 30),
("Warszawa", "Kraków", 40), ("Łódź", "Poznań", 21),
("Łódź", "Wrocław", 22), ("Łódź", "Katowice", 18),
("Poznań", "Wrocław", 18), ("Wrocław", "Katowice", 19),
("Katowice", "Kraków", 7),
]
graf = graf_nieskierowany(krawedzie)
odleglosc, poprzednik = dijkstra(graf, "Warszawa")
for miasto in sorted(odleglosc, key=odleglosc.get):
print(f"{miasto:9} {odleglosc[miasto]:3} " + " -> ".join(sciezka(poprzednik, miasto)))
Wynik i nieaktualne wpisy w kopcu
Wynik uruchomienia w Pythonie 3.14:
Warszawa 0 Warszawa
Łódź 13 Warszawa -> Łódź
Poznań 30 Warszawa -> Poznań
Katowice 31 Warszawa -> Łódź -> Katowice
Wrocław 35 Warszawa -> Łódź -> Wrocław
Kraków 38 Warszawa -> Łódź -> Katowice -> Kraków
Moduł heapq nie pozwala zmniejszyć priorytetu elementu, który już leży w kopcu. Dlatego przy każdej poprawie odległości dokładamy nowy wpis, a stare pomijamy przy zdejmowaniu (warunek if w in odwiedzone). W naszym przykładzie tak kończy się wpis “Kraków 40”: zostaje w kopcu do końca i jest odrzucany jako nieaktualny. Graf zapisujemy jako listę sąsiedztwa, czyli słownik, w którym każde miasto ma listę par (sąsiad, waga).
Odtwarzanie najkrótszej ścieżki
Sama tablica odległości mówi, ile kosztuje dojazd, ale nie którędy. Trasę odtwarza słownik poprzednik: zaczynamy od celu i cofamy się po poprzednikach aż do startu, a potem odwracamy listę. Dla Krakowa łańcuch wygląda tak: Kraków ← Katowice ← Łódź ← Warszawa.
Funkcja sciezka z kodu wyżej robi dokładnie to. Poprzednik zmienia się razem z odległością, więc po kroku 4 Kraków wskazuje już Katowice, a nie Warszawę. Przy grafie z wieloma równie krótkimi trasami ta metoda zwraca jedną z nich, tę, którą algorytm znalazł pierwszą.
Algorytm Dijkstry w C++ (priority_queue)
W C++ kolejkę priorytetową daje std::priority_queue z nagłówka <queue>. Według cppreference domyślnie na górze jest element największy, a wstawianie i zdejmowanie kosztują czas logarytmiczny. Komparator std::greater odwraca kolejność, więc na górze ląduje para o najmniejszej odległości.
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main() {
vector<string> miasta = {"Warszawa", "Łódź", "Poznań", "Wrocław", "Katowice", "Kraków"};
enum { WAW, LDZ, POZ, WRO, KAT, KRK };
const int n = miasta.size();
// lista sąsiedztwa: dla każdego miasta pary (sąsiad, waga)
vector<vector<pair<int, int>>> graf(n);
auto dodaj = [&](int a, int b, int waga) {
graf[a].push_back({b, waga});
graf[b].push_back({a, waga});
};
dodaj(WAW, LDZ, 13); dodaj(WAW, POZ, 30); dodaj(WAW, KRK, 40);
dodaj(LDZ, POZ, 21); dodaj(LDZ, WRO, 22); dodaj(LDZ, KAT, 18);
dodaj(POZ, WRO, 18); dodaj(WRO, KAT, 19); dodaj(KAT, KRK, 7);
const int INF = numeric_limits<int>::max();
vector<int> odleglosc(n, INF), poprzednik(n, -1);
vector<bool> odwiedzone(n, false);
// std::greater zamienia domyślny kopiec "największy na górze" na "najmniejszy na górze"
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> kolejka;
odleglosc[WAW] = 0;
kolejka.push({0, WAW});
while (!kolejka.empty()) {
auto [d, w] = kolejka.top();
kolejka.pop();
if (odwiedzone[w]) continue; // nieaktualny wpis w kolejce
odwiedzone[w] = true;
for (auto [sasiad, waga] : graf[w]) {
if (odwiedzone[sasiad]) continue;
if (d + waga < odleglosc[sasiad]) {
odleglosc[sasiad] = d + waga;
poprzednik[sasiad] = w;
kolejka.push({odleglosc[sasiad], sasiad});
}
}
}
vector<int> kolejnosc(n);
iota(kolejnosc.begin(), kolejnosc.end(), 0);
stable_sort(kolejnosc.begin(), kolejnosc.end(),
[&](int a, int b) { return odleglosc[a] < odleglosc[b]; });
for (int v : kolejnosc) {
vector<int> sciezka;
for (int x = v; x != -1; x = poprzednik[x]) sciezka.push_back(x);
reverse(sciezka.begin(), sciezka.end());
cout << miasta[v] << " " << odleglosc[v] << ": ";
for (size_t i = 0; i < sciezka.size(); ++i)
cout << (i ? " -> " : "") << miasta[sciezka[i]];
cout << "\n";
}
}
Wynik programu i szczegóły C++17
Program skompilowany w g++ 14 z flagą -std=c++17 wypisuje te same odległości i trasy co wersja w Pythonie:
Warszawa 0: Warszawa
Łódź 13: Warszawa -> Łódź
Poznań 30: Warszawa -> Poznań
Katowice 31: Warszawa -> Łódź -> Katowice
Wrocław 35: Warszawa -> Łódź -> Wrocław
Kraków 38: Warszawa -> Łódź -> Katowice -> Kraków
Zapis auto [d, w] to wiązanie strukturalne z C++17, które rozpakowuje parę na dwie zmienne. W starszym standardzie trzeba odczytać kolejka.top().first i .second. Miasta są tu numerami z typu wyliczeniowego enum, bo indeksy w wektorze są szybsze i prostsze niż słownik z napisami. W Windows konsola może pokazać polskie litery w nazwach miast jako krzaki, jeśli nie jest ustawiona na UTF-8.
Złożoność algorytmu Dijkstry
Z kopcem binarnym, jak w obu naszych wersjach, algorytm działa w czasie O((V + E) log V), gdzie V to liczba wierzchołków, a E liczba krawędzi. Każdy osiągalny wierzchołek jest przetwarzany raz, ale ten sam wierzchołek może mieć w kopcu kilka wpisów, jak Kraków w naszym przykładzie. Każda krawędź dokłada najwyżej jeden wpis, więc wszystkich operacji na kopcu jest O(V + E), a każda kosztuje logarytm z jego rozmiaru. Takie zapisy omawiamy w przeglądzie rodzajów algorytmów i ich złożoności.
Oryginalna wersja bez kopca, która za każdym razem przegląda wszystkie wierzchołki w poszukiwaniu najbliższego, działa w czasie O(V²). Dla grafu gęstego, w którym prawie każde miasto łączy się z każdym, to nie jest gorszy wybór. Opis algorytmu w Wikipedii podaje też wariant z kopcem Fibonacciego (Fredman i Tarjan, 1984) o złożoności O(E + V log V). W praktyce kopiec binarny wystarcza, bo prostsze struktury mają mniejsze stałe koszty.
W naszej wersji z leniwym pomijaniem wpisów kopiec może urosnąć do liczby krawędzi, a nie wierzchołków. Rząd złożoności się nie zmienia, bo w grafie prostym log E jest najwyżej dwa razy większy niż log V.
Dlaczego ujemne wagi psują wynik
Przy ujemnych wagach metoda Dijkstry nie gwarantuje poprawnego wyniku, bo uznaje odległość za ostateczną, zanim zobaczy wszystkie drogi. W części grafów trafi mimo to, ale nie da się na tym polegać. Najprostszy kontrprzykład ma trzy wierzchołki i krawędzie skierowane: S → A o wadze 2, S → B o wadze 5 i B → A o wadze -10.
g = {"S": [("A", 2), ("B", 5)], "A": [], "B": [("A", -10)]}
odleglosc, _ = dijkstra(g, "S")
print(odleglosc)
Wynik uruchomienia z funkcją dijkstra z tego tekstu:
{'S': 0, 'A': 2, 'B': 5}
Poprawna odległość do A to -5, drogą S → B → A (5 – 10). Algorytm odwiedza A w drugim kroku z odległością 2, bo to mniej niż 5 do B, i od tej chwili traktuje tę wartość jako ostateczną. Gdy później sprawdza krawędź B → A, wierzchołek A jest już odwiedzony. Dla tego samego grafu algorytm Bellmana-Forda zwraca poprawną odległość A = -5. Do grafów z ujemnymi wagami służy więc Bellman-Ford, a nie Dijkstra. Ma on jedno ograniczenie: jeśli ze startu da się dojść do cyklu o ujemnej sumie wag, najkrótsza odległość do wierzchołków za tym cyklem nie istnieje, bo każde okrążenie ją zmniejsza. Bellman-Ford taki cykl wykrywa i zgłasza. Przykład pokazuje też, że ten sam kod działa w grafie skierowanym, w którym krawędź prowadzi tylko w jedną stronę: wystarczy nie dopisywać krawędzi powrotnej.
Dijkstra a algorytm Prima, Bellman-Ford i A*
Czym różni się Dijkstra od algorytmu Prima?
Dijkstra szuka najkrótszych ścieżek z jednego punktu, a algorytm Prima buduje minimalne drzewo rozpinające, czyli najtańszy zestaw krawędzi łączący wszystkie wierzchołki. Nazwa “algorytm Prima-Dijkstry” bierze się stąd, że Dijkstra w tej samej notatce z 1959 roku opisał też drzewo rozpinające. Wspominał, że chodziło o połączenie punktów na panelu komputera jak najkrótszym drutem. Ten sam algorytm drzewa opisali wcześniej Vojtěch Jarník w 1930 roku i Robert Prim w 1957 roku, według opisu algorytmu Prima. Oba algorytmy wyglądają podobnie w kodzie, ale odpowiadają na inne pytania.
Czym różni się Dijkstra od algorytmu Bellmana-Forda?
Bellman-Ford liczy to samo co Dijkstra, czyli najkrótsze ścieżki z jednego wierzchołka, ale dopuszcza ujemne wagi i wykrywa ujemne cykle. Zamiast wybierać najbliższy wierzchołek, sprawdza wszystkie krawędzie V – 1 razy, więc działa w czasie O(V · E), wolniej niż Dijkstra z kopcem. Szczegóły opisuje hasło o algorytmie Bellmana-Forda. Gdy wszystkie wagi są nieujemne, Dijkstra jest szybszym wyborem.
Czym różni się Dijkstra od A*?
A to rozszerzenie metody Dijkstry, które przy wyborze kolejnego wierzchołka dodaje do znanej odległości oszacowanie drogi do celu, zwane heurystyką. Opublikowali go w 1968 roku Peter Hart, Nils Nilsson i Bertram Raphael ze Stanford Research Institute. Dijkstra to szczególny przypadek A, w którym heurystyka zawsze wynosi zero. A* szuka drogi do jednego celu i dzięki heurystyce zwykle odwiedza mniej wierzchołków. Dijkstra liczy odległości do wszystkich wierzchołków naraz.
Podsumowanie
Algorytm Dijkstry wyznacza najkrótsze ścieżki z jednego wierzchołka, wybierając zawsze najbliższy nieodwiedzony wierzchołek i poprawiając odległości jego sąsiadów. W naszym grafie sześciu miast z umownymi wagami trasa z Warszawy do Krakowa przez Łódź i Katowice kosztuje 38 i wygrywa z bezpośrednią krawędzią o wadze 40. Obie implementacje, w Pythonie z heapq i w C++ z std::priority_queue, dały ten sam wynik, a z kopcem binarnym działają w czasie O((V + E) log V). Gwarancję poprawnego wyniku dają tylko nieujemne wagi. Grafy z ujemnymi wagami liczy się algorytmem Bellmana-Forda, o ile nie ma w nich osiągalnego ujemnego cyklu. Następnym krokiem w serii są algorytmy na tych samych strukturach, opisane w przewodniku po algorytmach i strukturach danych. Wcześniejsze teksty serii to algorytm Euklidesa, sito Eratostenesa i sortowanie bąbelkowe.



