Zadania na rozgrzewkę. Pozwolą zapoznać Ci się konceptem i przygotują cię do kolejnych zadań.

Algorytm Dijkstry

Po tej lekcji będziesz umieć:

zaimplementować algorytm Dijkstry z kolejką priorytetową,
uzasadnić, dlaczego wagi muszą być nieujemne,
rozpoznać zadania, w których wierzchołkiem jest stan, a nie miasto.

1. Problem

Dany jest graf skierowany lub nieskierowany o $n$ wierzchołkach i $m$ krawędziach z wagami nieujemnymi oraz wierzchołek startowy $s$. Chcemy wyznaczyć $d(v)$, czyli długość najkrótszej ścieżki z $s$ do każdego $v$. Jest to problem SSSP (ang. single source shortest paths).

Formalnie, dla ścieżki $P = (v_0, v_1, \dots, v_k)$ jej koszt to \[ w(P) \;=\; \sum_{i=0}^{k-1} w(v_i, v_{i+1}), \] a szukamy \[ d(v) \;=\; \min_{P:\, s \rightsquigarrow v} w(P). \] Jeśli $v$ jest nieosiągalny, przyjmujemy $d(v) = \infty$.

2. Intuicja

Utrzymujemy zbiór $S$ wierzchołków domkniętych, dla których znamy już ostateczną odległość. Na starcie $S = \{s\}$ oraz $dist[s] = 0$.

W każdym kroku bierzemy wierzchołek $u \notin S$ o najmniejszym $dist[u]$, ogłaszamy jego odległość ostateczną i relaksujemy wszystkie krawędzie wychodzące z $u$: \[ dist[v] \;\leftarrow\; \min\bigl(dist[v],\; dist[u] + w(u,v)\bigr). \]

To algorytm zachłanny: raz domknięty wierzchołek nigdy nie zmienia swojej odległości.

3. Pseudokod

dijkstra(G, s):
    dist[v] = INF dla kazdego v
    dist[s] = 0
    Q = kolejka priorytetowa z para (0, s)

    dopoki Q niepusta:
        (d, u) = Q.pop_min()
        jesli d > dist[u]: pomin        # wpis przeterminowany
        dla (v, w) w sasiedzi(u):
            jesli d + w < dist[v]:
                dist[v] = d + w
                Q.push((dist[v], v))
    zwroc dist

4. Implementacja w C++

#include 
using namespace std;
using ll = long long;

const ll INF = (ll)1e18;

// g[u] = lista par (sasiad, waga)
vector dijkstra(int n, const vector>>& g, int src) {
    vector dist(n, INF);
    priority_queue, vector>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;   // leniwe usuwanie
        for (auto [v, w] : g[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

greater<> jest potrzebne, bo priority_queue jest domyślnie kopcem maksimum. Para $(dist, v)$ porównuje się leksykograficznie, więc porządek jest po odległości.

4.1. Odtwarzanie ścieżki

if (d + w < dist[v]) {
    dist[v] = d + w;
    parent[v] = u;
    pq.push({dist[v], v});
}

Następnie idziemy od $t$ po tablicy parent aż do $s$ i odwracamy wynik. Jeśli $dist[t] = \infty$, ścieżki nie ma.

5. Złożoność

Wariant	Struktura	Złożoność
Klasyczny, skan tablicy	tablica	$O(n^2 + m)$
Z kopcem binarnym	`priority_queue` / `set`	$O(m \log n)$
Z kopcem Fibonacciego	kopiec Fibonacciego	$O(m + n \log n)$

W praktyce na zawodach używa się wersji z priority_queue. Wersja $O(n^2)$ bywa lepsza dla grafów bardzo gęstych, gdzie $m = \Theta(n^2)$, na przykład $n = 2000$ i graf pełny.

Wersja z leniwym usuwaniem wrzuca do kolejki $O(m)$ wpisów, ale nie wymaga operacji decrease-key, dlatego jest prostsza i w praktyce szybsza od wariantu z set.

6. Dlaczego wagi muszą być nieujemne

Kontrprzykład:

$s \to a$ o wadze $1$,
$s \to b$ o wadze $2$,
$b \to a$ o wadze $-2$.

Dijkstra domyka $a$ z wartością $1$, bo w tym momencie jest to minimum w kolejce. Prawdziwa odległość to $d(a) = 2 + (-2) = 0$. Zachłanny niezmiennik opiera się na tym, że dalsza wędrówka po krawędziach nie może niczego skrócić. Ujemna krawędź to łamie.

Dla wag ujemnych: Bellman-Ford w $O(nm)$, a dla wszystkich par Floyd-Warshall w $O(n^3)$ albo algorytm Johnsona.

7. Szkic dowodu poprawności

Niezmiennik. W momencie zdjęcia wierzchołka $u$ z kolejki zachodzi $dist[u] = d(u)$.

Dowód nie wprost. Niech $u$ będzie pierwszym zdjętym wierzchołkiem, dla którego $dist[u] > d(u)$. Rozważmy najkrótszą ścieżkę $s \rightsquigarrow u$ i pierwszy wierzchołek $y$ na niej, który nie został jeszcze domknięty. Jego poprzednik $x$ jest domknięty, więc krawędź $(x,y)$ była już zrelaksowana, czyli $dist[y] = d(y)$. Ponieważ wagi są nieujemne, a $y$ leży na najkrótszej ścieżce do $u$: \[ dist[y] \;=\; d(y) \;\le\; d(u) \;<\; dist[u]. \] Zatem kolejka priorytetowa zdjęłaby $y$ przed $u$. Sprzeczność.

8. Typowe błędy

Przepełnienie zakresu. Przy $m = 2 \cdot 10^5$ krawędziach o wagach do $10^9$ sumy sięgają $10^{14}$, więc potrzebny jest long long.
Zbyt duże INF. Dla INF = LLONG_MAX wyrażenie dist[u] + w się przepełnia. Bezpieczna wartość to $10^{18}$. W powyższym kodzie problem nie występuje, bo do kolejki trafiają tylko wierzchołki osiągalne.
Brak leniwego usuwania. Pominięcie linii if (d > dist[u]) continue; nie psuje wyniku, ale powoduje wielokrotne przetwarzanie wierzchołków i może dać TLE.
Dijkstra przy ujemnych wagach. Częsty błąd, gdy wagi są liczone jako różnice.
Graf nieskierowany. Trzeba dodać obie krawędzie.

9. Warianty i rozszerzenia

9.1. BFS 0-1

Gdy wagi to tylko $0$ i $1$, zamiast kolejki priorytetowej wystarczy deque: krawędź o wadze $0$ wrzucamy na przód, o wadze $1$ na koniec. Złożoność $O(n + m)$.

9.2. Dijkstra na grafie stanów

Wierzchołkiem nie musi być pojedyncze miasto. Może to być para $(v, k)$, gdzie $k$ to liczba zużytych zniżek, albo $(v, p)$ z parzystością liczby przebytych krawędzi. Budujemy graf warstwowy o $O(nK)$ wierzchołkach i puszczamy zwykłą Dijkstrę. To najczęstsze zastosowanie olimpijskie.

9.3. Wiele źródeł

Wrzucamy na start wszystkie źródła z odległością $0$. Dostajemy $d(v) = \min_{s \in S} d(s, v)$, czyli odległość do najbliższego źródła.

9.4. Liczenie najkrótszych ścieżek

Dodajemy tablicę cnt. Przy $dist[u] + w < dist[v]$ ustawiamy $cnt[v] = cnt[u]$, a przy $dist[u] + w = dist[v]$ robimy $cnt[v] \mathrel{+}= cnt[u]$, modulo $10^9 + 7$.

9.5. Najszersza ścieżka

Zamiast minimalizować sumę, maksymalizujemy najwęższe gardło: \[ \max_{P:\, s \rightsquigarrow v} \; \min_{e \in P} w(e). \] Struktura algorytmu jest ta sama, zmienia się tylko operacja relaksacji.

10. Zadania

Maraton podstawowy
Czysta Dijkstra na grafie ważonym. Dobre pierwsze zadanie na sam algorytm.
Bajtockie Koleje Państwowe rozgrzewka grafowa
Wejście w modelowanie grafowe, zanim dojdą wagi.
Codeforces 20C, Dijkstra? podstawowy
Ta sama Dijkstra, ale trzeba wypisać samą ścieżkę, więc wymusza tablicę parent.
Ciężarówki 2 średni
Wariant gardłowy. Dijkstra nie jest tu rozwiązaniem wzorcowym, ale daje sensowny wynik częściowy.
Juror trudny, nieklasyczny
Trzeba skonstruować anty-test, na którym wersja z leniwym usuwaniem działa wolno. Świetne domknięcie tematu: sprawdza, czy naprawdę rozumiesz, skąd bierze się $O(m \log n)$.

Drzewo przedziałowe to struktura, która trzyma tablicę $a[1..n]$ i pozwala w czasie $O(\log n)$ odpowiadać na zapytania o przedział oraz modyfikować elementy.

pełny tekstowy opis cp-algorithms new tab

Codeforces EDU, ITMO Academy: Segment Tree part 1 i 2 new tab

USACO Guide, Point Update Range Sum new tab

Strona z wizualizacją drzewa przedziałowego new tab

    void Insert(int v, ll x) {
	v += BASE;
	tree[v] = x;
	v /= 2;
	while (v) {
		tree[v] = tree[v * 2] + tree[v * 2 + 1];
		v /= 2;
	}
}

ll Query(int a, int b) {
	ll ans = 0;
	a += BASE - 1;
	b += BASE + 1;
	int level = 1;
	while (a / 2 != b / 2) {
		if (!(a & 1)) ans += tree[a + 1];
		if (b & 1) ans += tree[b - 1];
		a /= 2;
		b /= 2;
		level++;
	}

	return ans;
}

    #include <bits/stdc++.h>
#define ll long long
using namespace std;

const int S = 1 << 20, MAXV = 1e9 + 10;
int t[2 * S + 10], pch[2 * S + 10];

void lazy(int v, int p, int k) {
  t[v * 2] += (k - p + 1) / 2 * pch[v];
  t[v * 2 + 1] += (k - p + 1) / 2 * pch[v];
  pch[2 * v] += pch[v], pch[2 * v + 1] += pch[v];
  pch[v] = 0;
}

void Insert(int v, int p, int k, int a, int b, ll w) {
  if (b < p || a > k) return;
  if (a <= p && b >= k) {
    pch[v] += w;
    t[v] += (k - p + 1) * w;
    return;
  }
  lazy(v, p, k);
  Insert(v * 2, p, (p + k) / 2, a, b, w);
  Insert(v * 2 + 1, (p + k) / 2 + 1, k, a, b, w);
  t[v] = t[v * 2] + t[v * 2 + 1];
}

ll Query(int v, int p, int k, int a, ll b) {
  if (b < p || a > k) return 0;
  if (a <= p && b >= k)
    return t[v];
  lazy(v, p, k);
  return Query(v * 2, p, (p + k) / 2, a, b) + Query(v * 2 + 1, (p + k) / 2 + 1, k, a, b);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

Zadania na rozgrzewkę. Pozwolą zapoznać Ci się konceptem i przygotują cię do kolejnych zadań.

Zadanie Megalopolis

Wyślij

poziom OI 2

Zadaj pytanie

Struktura grafu + DFS

Find & Union (DSU)

Zadania ćwiczeniowe (3)

Bankiet

Sieć komputerów

Dodatkowe: Unia Galaktyczna 1

Dijkstra

Materiały