Dijkstra-Algorithmus
Zuletzt aktualisiert
Der Dijkstra-Algorithmus findet den kürzesten Weg von einem Startknoten zu allen anderen Knoten in einem Graphen mit nicht negativen Kantengewichten. Er hält für jeden Knoten eine vorläufige Distanz, fixiert wiederholt den noch nicht fixierten Knoten mit der kleinsten vorläufigen Distanz und relaxiert dessen Kanten, wobei die Distanz eines Nachbarn aktualisiert wird, sobald eine kürzere Route über den aktuellen Knoten gefunden wird. Drücke oben auf Wiedergabe, um zu sehen, wie die Distanzen sinken, während jeder Knoten fixiert wird.
Die zentrale Einsicht ist gierig: Sobald der nächstgelegene, noch nicht fixierte Knoten gewählt ist, ist seine Distanz endgültig, weil jede andere Route zu ihm über einen Knoten führen müsste, der bereits weiter entfernt ist. Mit einer Prioritätswarteschlange auf Basis eines binären Heaps läuft Dijkstra in O((V + E) log V) Zeit. Er erfordert nicht negative Gewichte – verwende Bellman-Ford, wenn Kanten negativ sein können.
Zeit- und Speicherkomplexität
| Implementierung | Komplexität | Anmerkungen |
|---|---|---|
| Binärer Heap | O((V + E) log V) | Die übliche, praktische Wahl |
| Array-Durchlauf | O(V²) | Einfacher; passend für dichte Graphen |
| Speicher | O(V) | Distanzen + Prioritätswarteschlange |
| Erfordert | Nicht negative Gewichte | Negative Kanten brechen die gierige Wahl |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Setze die Distanz der Quelle auf 0 und alle anderen auf unendlich. |
| 2 | Wähle den noch nicht fixierten Knoten mit der kleinsten vorläufigen Distanz. |
| 3 | Markiere ihn als fixiert – seine kürzeste Distanz ist nun endgültig. |
| 4 | Berechne für jeden Nachbarn Distanz-über-den-aktuellen + Kantengewicht. |
| 5 | Ist sie kleiner als die aktuelle Distanz des Nachbarn, relaxiere sie. |
| 6 | Wiederhole, bis alle erreichbaren Knoten fixiert sind. |
Durchgerechnetes Beispiel
Kürzeste Wege von der Quelle A im Graphen mit den Kanten A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Schritt | Fixieren | Distanzen | Aktion |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Initialisieren: Quelle A=0, alle anderen unendlich. |
| 1 | A (0) | B=4, C=1, D=∞ | Relaxiere die Kanten von A: setze B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Über C: B=1+2=3 schlägt 4; D=1+5=6. |
| 3 | B (3) | D=4 | Über B: D=3+1=4 schlägt 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Fixiere D; nichts mehr zu relaxieren. Fertig. |
Wann man den Dijkstra-Algorithmus verwendet
| Verwende ihn, wenn | Vermeide ihn, wenn |
|---|---|
| Alle Kantengewichte nicht negativ sind | Eine Kante negativ sein kann – verwende Bellman-Ford |
| Du kürzeste Wege von einer Quelle zu allen Knoten brauchst | Du kürzeste Wege zwischen allen Paaren brauchst – Floyd-Warshall ist einfacher |
| Der Graph gewichtet ist und du exakte Distanzen willst | Der Graph ungewichtet ist – reines BFS ist schneller und einfacher |
| Du einen guten Heap bzw. eine gute Prioritätswarteschlange hast | Du ein einziges Ziel schnell mit einer Heuristik erreichen willst – verwende A* |
Dijkstra's Algorithm-Code
Eine saubere, lauffähige Dijkstra's Algorithm-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Dijkstra's Algorithm-Code in 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-Code in 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-Code in 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-Code in 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-Code in 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}FAQ zum Dijkstra-Algorithmus
Wie hoch ist die Zeitkomplexität des Dijkstra-Algorithmus?
Mit einer Prioritätswarteschlange auf Basis eines binären Heaps läuft er in
O((V + E) log V). Eine einfache Variante, die in jedem Schritt ein Array nach dem Minimum durchsucht, ist O(V²), was bei dichten Graphen sogar schneller sein kann. Beide benötigen O(V) Speicher.Warum funktioniert Dijkstra nicht mit negativen Kantengewichten?
Dijkstra nimmt an, dass die Distanz endgültig ist, sobald der nächstgelegene, noch nicht fixierte Knoten fixiert wurde. Eine negative Kante könnte später einen kürzeren Weg zu einem bereits fixierten Knoten schaffen und diese Annahme brechen. Für Graphen mit negativen Gewichten verwende den Bellman-Ford-Algorithmus.
Was ist der Unterschied zwischen Dijkstra und BFS?
BFS findet kürzeste Wege durch Zählen der Kanten (jedes Kantengewicht ist praktisch 1) mit einer einfachen Warteschlange. Dijkstra verallgemeinert dies auf gewichtete Graphen, indem stets der Knoten mit der kleinsten Gesamtdistanz mithilfe einer Prioritätswarteschlange expandiert wird. In einem ungewichteten Graphen liefern beide dieselben Wege.
Was ist der Unterschied zwischen Dijkstra und der A*-Suche?
A* ist Dijkstra plus einer Heuristik, die die verbleibende Distanz zu einem Ziel schätzt und die Suche so auf dieses Ziel lenkt, statt sich gleichmäßig in alle Richtungen auszubreiten. Ist die Heuristik null, entartet A* genau zu Dijkstra. Verwende A*, wenn du ein einziges Ziel und eine gute zulässige Heuristik hast; verwende Dijkstra, wenn du Distanzen zu allen Knoten brauchst.
Wann sollte ich Dijkstra statt Bellman-Ford verwenden?
Verwende Dijkstra immer dann, wenn alle Kantengewichte nicht negativ sind – er ist schneller mit
O((V + E) log V) gegenüber O(V·E) bei Bellman-Ford. Wähle Bellman-Ford nur, wenn Kanten negativ sein können oder du negative Zyklen erkennen musst. Bei nicht negativen Graphen ist Dijkstra fast immer die bessere Wahl.Kann Dijkstra einen Knoten erneut besuchen, nachdem er fixiert wurde?
Nein – sobald ein Knoten fixiert ist, ist seine Distanz endgültig und wird nie wieder relaxiert. Eine häufige Falle bei Heap-Implementierungen ist es, veraltete Einträge in der Prioritätswarteschlange zu belassen, nachdem sich die Distanz eines Knotens verbessert hat; du musst einen entnommenen Knoten überspringen, wenn er bereits fixiert ist (seine entnommene Distanz übersteigt die gespeicherte Distanz). Diese Prüfung zu vergessen liefert weiterhin korrekte Antworten, verschwendet aber Arbeit.
Verwandte Ressourcen
Mehr Visualisierungen
