Algoritmo di Dijkstra
Ultimo aggiornamento
L'algoritmo di Dijkstra trova il cammino minimo da un nodo sorgente a tutti gli altri nodi in un grafo con pesi degli archi non negativi. Tiene una distanza provvisoria per ogni nodo, fissa ripetutamente il nodo non ancora fissato con la distanza provvisoria più piccola e ne rilassa gli archi, aggiornando la distanza di un vicino ogni volta che trova un percorso più breve passando per il nodo corrente. Premi play qui sopra per vedere le distanze scendere man mano che ogni nodo viene fissato.
L'idea chiave è greedy: una volta scelto il nodo non fissato più vicino, la sua distanza è definitiva, perché qualsiasi altro percorso verso di lui dovrebbe passare per un nodo che è già più lontano. Con una coda di priorità basata su heap binario, Dijkstra richiede tempo O((V + E) log V). Richiede pesi non negativi: usa Bellman-Ford se gli archi possono essere negativi.
Complessità temporale e spaziale
| Implementazione | Complessità | Note |
|---|---|---|
| Heap binario | O((V + E) log V) | La scelta comune e pratica |
| Scansione dell'array | O(V²) | Più semplice; va bene per grafi densi |
| Spazio | O(V) | Distanze + coda di priorità |
| Richiede | Pesi non negativi | Gli archi negativi rompono la scelta greedy |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Imposta la distanza della sorgente a 0 e tutte le altre a infinito. |
| 2 | Scegli il nodo non fissato con la distanza provvisoria più piccola. |
| 3 | Segnalo come fissato: la sua distanza minima ora è definitiva. |
| 4 | Per ogni vicino, calcola la distanza attraverso il nodo corrente + il peso dell'arco. |
| 5 | Se è minore della distanza attuale del vicino, rilassalo. |
| 6 | Ripeti finché tutti i nodi raggiungibili non sono fissati. |
Esempio svolto
Cammini minimi dalla sorgente A sul grafo con gli archi A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Passo | Fissa | Distanze | Azione |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Inizializza: sorgente A=0, tutte le altre a infinito. |
| 1 | A (0) | B=4, C=1, D=∞ | Rilassa gli archi da A: imposta B=4, C=1. |
| 2 | C (1) | B=3, D=6 | Passando per C: B=1+2=3 batte 4; D=1+5=6. |
| 3 | B (3) | D=4 | Passando per B: D=3+1=4 batte 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Fissa D; non resta nulla da rilassare. Fatto. |
Quando usare l'algoritmo di Dijkstra
| Usalo quando | Evitalo quando |
|---|---|
| Tutti i pesi degli archi sono non negativi | Un arco qualsiasi può essere negativo: usa Bellman-Ford |
| Ti servono i cammini minimi da una sorgente a tutti i nodi | Ti servono i cammini minimi tra tutte le coppie: Floyd-Warshall è più semplice |
| Il grafo è pesato e vuoi distanze esatte | Il grafo non è pesato: una semplice BFS è più veloce e più semplice |
| Hai a disposizione un buon heap o una buona coda di priorità | Vuoi raggiungere in fretta un'unica destinazione con un'euristica: usa A* |
Codice Dijkstra's Algorithm
Un'implementazione di Dijkstra's Algorithm pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Dijkstra's Algorithm 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}")Codice Dijkstra's Algorithm 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"));Codice Dijkstra's Algorithm 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}Codice Dijkstra's Algorithm 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}Codice Dijkstra's Algorithm 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}Domande frequenti sull'algoritmo di Dijkstra
Qual è la complessità temporale dell'algoritmo di Dijkstra?
Con una coda di priorità basata su heap binario richiede
O((V + E) log V). Una versione semplice che a ogni passo scorre un array per trovare il minimo è O(V²), che sui grafi densi può essere perfino più veloce. Entrambe usano spazio O(V).Perché Dijkstra non funziona con pesi negativi?
Dijkstra presume che, una volta fissato il nodo non fissato più vicino, quella distanza sia definitiva. Un arco negativo potrebbe creare in seguito un percorso più breve verso un nodo già fissato, violando questa ipotesi. Per i grafi con pesi negativi usa l'algoritmo di Bellman-Ford.
Qual è la differenza tra Dijkstra e BFS?
La BFS trova i cammini minimi contando gli archi (ogni arco pesa di fatto 1) usando una coda semplice. Dijkstra generalizza questa idea ai grafi pesati espandendo sempre il nodo con la distanza totale più piccola, grazie a una coda di priorità. Su un grafo non pesato i due producono gli stessi percorsi.
Qual è la differenza tra Dijkstra e la ricerca A*?
A* è Dijkstra più un'euristica che stima la distanza rimanente verso una destinazione, così guida la ricerca verso quell'obiettivo invece di espandersi in modo uniforme in tutte le direzioni. Quando l'euristica vale zero, A* diventa esattamente Dijkstra. Usa A* quando hai un'unica destinazione e una buona euristica ammissibile; usa Dijkstra quando ti servono le distanze verso ogni nodo.
Quando conviene usare Dijkstra invece di Bellman-Ford?
Usa Dijkstra ogni volta che tutti i pesi degli archi sono non negativi: è più veloce,
O((V + E) log V) contro O(V·E) di Bellman-Ford. Scegli Bellman-Ford solo quando gli archi possono essere negativi o devi rilevare cicli negativi. Sui grafi con pesi non negativi Dijkstra è quasi sempre la scelta migliore.Dijkstra può rivisitare un nodo dopo averlo fissato?
No: una volta fissato un nodo, la sua distanza è definitiva e non viene più rilassato. Una trappola comune nelle implementazioni con heap è lasciare voci vecchie nella coda di priorità dopo che la distanza di un nodo è migliorata; devi saltare un nodo estratto se è già fissato (la sua distanza estratta supera quella registrata). Dimenticare questo controllo dà comunque risposte corrette, ma spreca lavoro.
Risorse correlate
Altre visualizzazioni
