Cos'è dijkstra?

Algoritmo di Dijkstra

L'Algoritmo di Dijkstra, inventato dallo scienziato informatico Edsger W. Dijkstra nel 1959, è un algoritmo per trovare il percorso più breve tra i nodi in un grafo. In particolare, produce un albero dei cammini minimi da un nodo sorgente a tutti gli altri nodi del grafo quando i pesi sugli archi sono non negativi. È spesso usato nel routing e come sottoroutine in altri algoritmi di grafi.

Come Funziona:

L'algoritmo di Dijkstra funziona mantenendo un insieme di nodi per cui è già stato calcolato il cammino minimo (l'insieme "risolto") e un insieme di nodi per cui il cammino minimo non è ancora stato calcolato. Inizia con il nodo sorgente e assegna a tutti gli altri nodi una distanza infinita. A ogni iterazione, seleziona il nodo non risolto con la distanza più piccola dal nodo sorgente (questo nodo è il più vicino tra quelli ancora da esplorare), lo aggiunge all'insieme "risolto" e aggiorna le distanze dei suoi vicini. L'aggiornamento delle distanze consiste nel verificare se il cammino attraverso il nodo appena aggiunto all'insieme "risolto" è più breve del cammino corrente verso il vicino.

Passi dell'Algoritmo:

Assegna un valore di distanza a ogni nodo: imposta a zero il nodo sorgente e a infinito tutti gli altri nodi.
Imposta il nodo sorgente come nodo corrente.
Per il nodo corrente, considera tutti i suoi vicini non visitati e calcola la loro distanza temporanea dal nodo sorgente (la distanza è la somma della distanza dal nodo sorgente al nodo corrente e la distanza dal nodo corrente al vicino). Se questa distanza temporanea è minore della distanza corrente registrata, sostituisci la distanza registrata con questa distanza temporanea.
Una volta che hai considerato tutti i vicini non visitati del nodo corrente, marca il nodo corrente come visitato e rimuovilo dall'insieme dei nodi non visitati. Un nodo visitato non sarà mai più controllato.
Seleziona il successivo nodo non visitato con la distanza più piccola (dal nodo sorgente) e imposta questo come nuovo nodo corrente, quindi torna al passaggio 3.
Continua fino a quando tutti i nodi sono stati visitati o non ci sono più nodi non visitati con una distanza minore di infinito.

Complessità Computazionale:

La complessità computazionale dell'algoritmo di Dijkstra dipende dalla struttura dati utilizzata per implementare la coda di priorità dei nodi non visitati. Con una coda di priorità implementata come un array semplice, la complessità è O(V<sup>2</sup>), dove V è il numero di vertici. Con una coda di priorità implementata come un heap binario, la complessità è O((V + E)log V), dove E è il numero di archi. Con un heap di Fibonacci, la complessità può essere ridotta a O(E + V log V).

Limitazioni:

Pesi Negativi: L'algoritmo di Dijkstra non funziona correttamente con grafi che contengono archi con pesi negativi. In presenza di pesi negativi, è necessario utilizzare l'algoritmo di Bellman-Ford.
Cicli Negativi: L'algoritmo di Dijkstra non può gestire grafi con cicli negativi. Un ciclo negativo è un ciclo in cui la somma dei pesi degli archi è negativa. In questo caso, il cammino più corto non è ben definito poiché è possibile diminuire la distanza totale percorrendo il ciclo negativo un numero arbitrario di volte.

Applicazioni:

L'algoritmo di Dijkstra ha molte applicazioni pratiche, tra cui:

Routing di Rete: Utilizzato nei protocolli di routing per determinare il percorso più breve tra due router in una rete.
Sistemi di Navigazione: Utilizzato nei sistemi di navigazione GPS per calcolare il percorso più breve tra due località.
Robotica: Utilizzato nella pianificazione del percorso per trovare il percorso più efficiente per un robot per navigare in un ambiente.
Operazioni su Grafi: Utilizzato come sottoroutine in molti altri algoritmi di grafi, come l'algoritmo A*.

Concetti importanti correlati:

dilemma del porcospino

dilemma del prigioniero