Calcolatore del Percorso più Breve di Dijkstra
Trova il percorso più breve tra i nodi in un grafo pesato utilizzando l'algoritmo di Dijkstra. Include visualizzazione interattiva del grafo, tracciamento passo-passo della coda di priorità e visualizzazione dell'albero dei percorsi minimi.
Il tuo ad blocker ci impedisce di mostrare annunci
MiniWebtool è gratuito grazie agli annunci. Se questo strumento ti è stato utile, sostienici con Premium (senza annunci + più veloce) oppure inserisci MiniWebtool.com nella whitelist e ricarica la pagina.
- Oppure passa a Premium (senza annunci)
- Consenti gli annunci per MiniWebtool.com, poi ricarica
Calcolatore del Percorso più Breve di Dijkstra
Benvenuti nel Calcolatore del percorso più breve di Dijkstra, uno strumento interattivo per trovare i percorsi minimi in grafi pesati utilizzando l'algoritmo di Dijkstra. Che tu sia uno studente di informatica che studia la teoria dei grafi, un professionista di networking che analizza i protocolli di routing o uno sviluppatore che implementa il pathfinding, questo calcolatore offre un'esplorazione visiva e passo-passo di uno degli algoritmi più fondamentali dell'informatica.
Cos'è l'Algoritmo di Dijkstra?
L'algoritmo di Dijkstra, ideato dall'informatico olandese Edsger W. Dijkstra nel 1956, è un algoritmo di ricerca su grafi che risolve il problema del percorso più breve da sorgente singola per un grafo pesato con pesi degli archi non negativi. Dato un nodo sorgente, trova il cammino minimo tra quel nodo e ogni altro nodo del grafo.
L'algoritmo funziona mantenendo un insieme di nodi non visitati e selezionando ripetutamente il nodo non visitato con la distanza provvisoria più piccola (una strategia greedy). Questo è ciò che lo rende elegante ed efficiente: una volta che un nodo viene "visitato", la sua distanza minima è garantita come definitiva.
Pseudocodice dell'algoritmo
per ogni nodo v nel Grafo:
dist[v] ← ∞
prev[v] ← non definito
dist[sorgente] ← 0
Q ← coda di priorità di tutti i nodi
mentre Q non è vuota:
u ← nodo in Q con dist[u] minima
rimuovi u da Q
per ogni vicino v di u ancora in Q:
alt ← dist[u] + peso(u, v)
se alt < dist[v]:
dist[v] ← alt // rilassamento
prev[v] ← u
restituisci dist[], prev[]
Formula Fondamentale
Dove:
- d[u] = attuale distanza minima nota dalla sorgente al nodo u
- w(u, v) = peso dell'arco da u a v
- d[v] = attuale distanza minima nota dalla sorgente al nodo v
Come Usare Questo Calcolatore
- Definisci gli archi del grafo: Inserisci gli archi nel formato
sorgente, destinazione, peso, uno per riga. Ogni riga rappresenta un collegamento tra due nodi. - Scegli il tipo di grafo: Seleziona "Non orientato" per archi a doppio senso (come le strade) o "Orientato" per archi a senso unico (come i link web).
- Imposta il nodo sorgente: Inserisci il nodo di partenza dal quale verranno calcolati i percorsi.
- Trova i percorsi più brevi: Clicca sul pulsante per eseguire l'algoritmo. Esplora la visualizzazione grafica, la tabella delle distanze e la traccia passo-passo.
- Naviga tra i passaggi: Usa i pulsanti Avanti/Indietro per vedere l'esecuzione dell'algoritmo un passo alla volta.
Comprendere i Risultati
Tabella delle Distanze
Mostra la distanza minima dalla sorgente a ogni nodo, insieme al percorso completo. I nodi contrassegnati con ∞ non sono raggiungibili dalla sorgente.
Visualizzazione del Grafo
Il canvas interattivo mostra il tuo grafo con nodi e archi codificati per colore:
- Nodo blu = Nodo sorgente
- Nodi verdi = Visitati (distanza definitiva)
- Nodo arancione = In corso di elaborazione
- Nodi grigi = Non ancora visitati
- Archi verdi = Albero dei percorsi più brevi
Traccia Passo-Passo
Mostra l'esecuzione dell'algoritmo, incluse le estrazioni dalla coda di priorità, i rilassamenti degli archi e gli aggiornamenti delle distanze ad ogni step. Questo è fondamentale per capire come opera l'algoritmo.
Complessità Temporale
L'efficienza dell'algoritmo di Dijkstra dipende dalla struttura dati utilizzata per la coda di priorità:
| Coda di Priorità | Complessità Temporale | Ideale per |
|---|---|---|
| Heap Binario | \( O((V + E) \log V) \) | Uso generale, grafi sparsi |
| Heap di Fibonacci | \( O(V \log V + E) \) | Grafi densi (teorico) |
| Array (senza heap) | \( O(V^2) \) | Grafi molto densi, V piccolo |
Dove V è il numero di vertici (nodi) ed E è il numero di archi. Questo calcolatore utilizza un'implementazione con heap binario.
Grafi Orientati vs. Non Orientati
- Grafo non orientato: Un arco tra A e B significa che puoi viaggiare sia A→B che B→A. Esempi: reti stradali, reti di amicizia.
- Grafo orientato: Un arco da A a B permette solo il viaggio A→B. Esempi: collegamenti ipertestuali web, follower di Twitter, rotte aeree.
Limitazioni dell'Algoritmo di Dijkstra
- Nessun peso negativo: L'algoritmo di Dijkstra produce risultati errati con pesi negativi. Usa Bellman-Ford per grafi con pesi negativi.
- Sorgente singola: Trova i percorsi da una sola sorgente. Per percorsi tra tutte le coppie, usa Floyd-Warshall.
- Nessun ciclo negativo: I cicli negativi rendono i percorsi minimi non definiti.
Applicazioni Reali
Navigazione GPS
I servizi di mappatura utilizzano varianti di Dijkstra (spesso con euristiche A*) per trovare il percorso più veloce tra due località.
Routing di Rete
I protocolli di routing internet come OSPF e IS-IS utilizzano Dijkstra per calcolare i percorsi più brevi attraverso le topologie di rete.
Analisi dei Social Network
Trovare il percorso di connessione più breve tra gli utenti (gradi di separazione) e identificare i nodi influenti.
Sviluppo di Videogiochi
Il pathfinding degli NPC nei videogiochi utilizza Dijkstra o A* per navigare nelle mappe di gioco e trovare percorsi di movimento ottimali.
Domande Frequenti
Cos'è l'algoritmo di Dijkstra?
È un algoritmo che trova il percorso più breve tra un nodo iniziale e tutti gli altri in un grafo con pesi non negativi.
Può gestire pesi negativi?
No, richiede pesi non negativi. Per i pesi negativi, è necessario l'algoritmo di Bellman-Ford.
Qual è la differenza tra grafi orientati e non orientati?
Nei grafi orientati gli archi hanno una direzione specifica, in quelli non orientati la connessione è bidirezionale.
Risorse Aggiuntive
Cita questo contenuto, pagina o strumento come:
"Calcolatore del Percorso più Breve di Dijkstra" su https://MiniWebtool.com/it// di MiniWebtool, https://MiniWebtool.com/
dal team miniwebtool. Aggiornato: 19 feb 2026
Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.