Algorytm Dijkstry
Ostatnia aktualizacja
Algorytm Dijkstry znajduje najkrótszą ścieżkę od węzła źródłowego do każdego innego węzła w grafie z nieujemnymi wagami krawędzi. Przechowuje tymczasową odległość każdego węzła, wielokrotnie ustala nieustalony węzeł o najmniejszej tymczasowej odległości i relaksuje jego krawędzie, czyli aktualizuje odległość sąsiada za każdym razem, gdy znajdzie krótszą trasę przez bieżący węzeł. Kliknij odtwarzanie powyżej i zobacz, jak odległości maleją, gdy kolejne węzły są ustalane.
Kluczowa idea jest zachłanna: gdy wybrany zostanie najbliższy nieustalony węzeł, jego odległość jest ostateczna, bo każda inna trasa do niego musiałaby prowadzić przez węzeł, który jest już dalej. Z kolejką priorytetową opartą na kopcu binarnym algorytm Dijkstry działa w czasie O((V + E) log V). Wymaga nieujemnych wag: jeśli krawędzie mogą być ujemne, użyj algorytmu Bellmana-Forda.
Złożoność czasowa i pamięciowa
| Implementacja | Złożoność | Uwagi |
|---|---|---|
| Kopiec binarny | O((V + E) log V) | Popularny, praktyczny wybór |
| Przeglądanie tablicy | O(V²) | Prostsze; dobre dla gęstych grafów |
| Pamięć | O(V) | Odległości + kolejka priorytetowa |
| Wymaga | Nieujemnych wag | Ujemne krawędzie psują wybór zachłanny |
Krok po kroku
| Krok | Co się dzieje |
|---|---|
| 1 | Ustaw odległość źródła na 0, a wszystkich pozostałych na nieskończoność. |
| 2 | Wybierz nieustalony węzeł o najmniejszej tymczasowej odległości. |
| 3 | Oznacz go jako ustalony: jego najkrótsza odległość jest teraz ostateczna. |
| 4 | Dla każdego sąsiada oblicz odległość przez bieżący węzeł + wagę krawędzi. |
| 5 | Jeśli jest mniejsza niż bieżąca odległość sąsiada, zrelaksuj ją. |
| 6 | Powtarzaj, aż wszystkie osiągalne węzły będą ustalone. |
Przykład krok po kroku
Najkrótsze ścieżki od źródła A w grafie z krawędziami A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Krok | Ustal | Odległości | Działanie |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Inicjalizacja: źródło A=0, wszystkie pozostałe nieskończoność. |
| 1 | A (0) | B=4, C=1, D=∞ | Relaksuj krawędzie z A: ustaw B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Przez C: B=1+2=3 jest lepsze niż 4; D=1+5=6. |
| 3 | B (3) | D=4 | Przez B: D=3+1=4 jest lepsze niż 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Ustal D; nie ma już nic do relaksacji. Koniec. |
Kiedy używać algorytmu Dijkstry
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Wszystkie wagi krawędzi są nieujemne | Któraś krawędź może być ujemna: użyj algorytmu Bellmana-Forda |
| Potrzebujesz najkrótszych ścieżek z jednego źródła do wszystkich węzłów | Potrzebujesz najkrótszych ścieżek między wszystkimi parami: Floyd-Warshall jest prostszy |
| Graf jest ważony i chcesz dokładnych odległości | Graf nie ma wag: zwykłe BFS jest szybsze i prostsze |
| Masz do dyspozycji dobry kopiec lub kolejkę priorytetową | Chcesz szybko dotrzeć do jednego celu z pomocą heurystyki: użyj A* |
Dijkstra's Algorithm: kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Dijkstra's Algorithm w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Dijkstra's Algorithm: kod (Python)
Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Dijkstra's Algorithm: kod (JavaScript)
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Dijkstra's Algorithm: kod (Java)
Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Dijkstra's Algorithm: kod (C++)
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Dijkstra's Algorithm: kod (C)
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}Algorytm Dijkstry: najczęstsze pytania
Jaka jest złożoność czasowa algorytmu Dijkstry?
Z kolejką priorytetową opartą na kopcu binarnym działa w
O((V + E) log V). Prosta wersja, która w każdym kroku przegląda tablicę w poszukiwaniu minimum, ma złożoność O(V²) i w gęstych grafach może być nawet szybsza. Obie zużywają O(V) pamięci.Dlaczego algorytm Dijkstry nie działa z ujemnymi wagami krawędzi?
Algorytm Dijkstry zakłada, że gdy ustali najbliższy nieustalony węzeł, jego odległość jest ostateczna. Ujemna krawędź mogłaby później utworzyć krótszą ścieżkę do już ustalonego węzła i złamać to założenie. W grafach z ujemnymi wagami użyj algorytmu Bellmana-Forda.
Czym różni się algorytm Dijkstry od BFS?
BFS znajduje najkrótsze ścieżki, licząc krawędzie (każda krawędź ma w praktyce wagę 1), za pomocą zwykłej kolejki. Algorytm Dijkstry uogólnia to na grafy ważone, zawsze rozwijając węzeł o najmniejszej łącznej odległości za pomocą kolejki priorytetowej. W grafie bez wag oba dają te same ścieżki.
Czym różni się algorytm Dijkstry od A*?
A* to algorytm Dijkstry z heurystyką szacującą pozostałą odległość do celu, dzięki czemu kieruje przeszukiwanie w stronę celu, zamiast rozszerzać je równomiernie we wszystkich kierunkach. Gdy heurystyka wynosi zero, A* staje się dokładnie algorytmem Dijkstry. Używaj A*, gdy masz jeden cel i dobrą, dopuszczalną heurystykę; używaj algorytmu Dijkstry, gdy potrzebujesz odległości do każdego węzła.
Kiedy użyć algorytmu Dijkstry zamiast Bellmana-Forda?
Używaj algorytmu Dijkstry zawsze, gdy wszystkie wagi krawędzi są nieujemne: jest szybszy,
O((V + E) log V) wobec O(V·E) w algorytmie Bellmana-Forda. Wybierz Bellmana-Forda tylko wtedy, gdy krawędzie mogą być ujemne albo musisz wykrywać ujemne cykle. W grafach z nieujemnymi wagami Dijkstra jest prawie zawsze lepszym wyborem.Czy algorytm Dijkstry może ponownie odwiedzić ustalony węzeł?
Nie. Gdy węzeł zostanie ustalony, jego odległość jest ostateczna i nigdy nie jest ponownie relaksowana. Częsta pułapka w implementacjach z kopcem to nieaktualne wpisy w kolejce priorytetowej po poprawie odległości węzła; musisz pominąć pobrany węzeł, jeśli jest już ustalony (jego pobrana odległość przekracza zapisaną). Pominięcie tego sprawdzenia nadal daje poprawne wyniki, ale marnuje pracę.
Powiązane materiały
Więcej wizualizacji
