Definitivo
In coda
Archi esaminati

  • Attuale
  • In coda
  • Definitivo
  • Percorso
Un clic su un nodo imposta

Di più sull'algoritmo di Dijkstra

Algoritmo di Dijkstra

L'algoritmo di Dijkstra trova il percorso più breve da una partenza a ogni altro nodo quando gli archi hanno una lunghezza, come le strade tra città. Si espande dalla partenza verso l'esterno, prendendo sempre il nodo più vicino che non ha ancora finito. Fai clic su un nodo per partire da lì, scegli un arrivo se vuoi e procedi passo per passo per vedere la coda, ogni distanza che scende quando spunta un percorso più breve, e il percorso più breve che appare. Premi Avvia per guardare la ricerca, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Fai clic su un nodo per farne la partenza; passa il clic su Arrivo e fai clic su un altro nodo per cercare un percorso più breve fino a lì. Il numero su ogni arco è la sua lunghezza, il numero su ogni nodo la sua distanza più breve finora, e la riga sotto il grafo è la coda, a partire dal più vicino. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Fai clic su un nodo per farne la partenza. Per cercare un percorso, passa il clic su Arrivo e fai clic su un altro nodo.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto della ricerca.
  3. Osserva la coda sotto il grafo e la distanza su ogni nodo. Nuovo grafo crea un altro grafo da provare.

Come funziona l'algoritmo di Dijkstra

Dai alla partenza distanza 0 e a ogni altro nodo infinito, e metti la partenza in una coda. Poi ripeti: prendi il nodo in coda con la distanza più piccola e segna quella distanza come definitiva. Per ogni suo vicino non definitivo, somma la lunghezza dell'arco alla distanza del nodo. Se la somma è minore della distanza attuale del vicino, diventa la sua nuova distanza, il nodo viene ricordato come via per arrivarci e il vicino entra in coda, se non c'era già. Quando la coda è vuota, ogni nodo raggiungibile ha la sua distanza più breve.

Perché il nodo più vicino è definitivo

Quando un nodo è il più vicino in coda, ogni altro percorso fino a lui deve uscire dalla parte finita del grafo attraverso un nodo in coda, che dista almeno altrettanto, e poi aggiungere archi che non possono essere negativi. Quindi nessun altro percorso può essere più breve. Per questo un arrivo è certo solo quando esce dalla coda, non quando viene raggiunto la prima volta, e per questo l'algoritmo di Dijkstra fallisce con archi negativi: lì serve l'algoritmo di Bellman–Ford. Quando ogni arco ha lunghezza 1, l'algoritmo di Dijkstra fa lo stesso della visita in ampiezza.

Domande frequenti

Che cos'è l'algoritmo di Dijkstra?

Un modo per trovare i percorsi più brevi da un nodo di partenza a tutti gli altri nodi di un grafo i cui archi hanno lunghezze pari a zero o più. Prende ogni volta il nodo non finito più vicino, rende definitiva la sua distanza e usa i suoi archi per accorciare le distanze dei vicini.

Perché l'algoritmo di Dijkstra non funziona con archi negativi?

Rende definitiva la distanza di un nodo appena quel nodo è il più vicino in coda. Un arco negativo trovato più tardi potrebbe ancora riportare a quel nodo per una via più breve, e la distanza definitiva sarebbe sbagliata. L'algoritmo di Bellman–Ford gestisce gli archi negativi, purché non ci sia un ciclo con totale negativo.

Che differenza c'è tra Dijkstra e BFS?

La visita in ampiezza conta gli archi e usa una coda semplice. L'algoritmo di Dijkstra somma le lunghezze degli archi e usa una coda di priorità che dà sempre il nodo più vicino. Se ogni arco ha lunghezza 1, entrambi trovano le stesse distanze.

Quanto è veloce l'algoritmo di Dijkstra?

Con un heap binario come coda di priorità, il lavoro cresce con (V + E) log V per V nodi ed E archi. Con un heap di Fibonacci è E + V log V. L'app tiene la coda come lista ordinata, semplice da mostrare e adatta a grafi piccoli.

Il mio grafo viene inviato da qualche parte?

No. Il grafo viene creato e visitato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor