Informatica · Algoritmi
Laboratorio di algoritmi sui grafi pesati
Lo stesso grafo per tre domande diverse: qual è il percorso più corto? Come collegare tutti i nodi con il minor peso totale?
Dijkstra fissa ogni volta il nodo non ancora visitato con la distanza provvisoria più piccola. Richiede pesi non negativi; qui sono tutti da 1 a 20.
Grafo pronto. Premi Avvia oppure Passo successivo.
Passo0 / 0
Archi scelti0
Distanza alla meta—
Archi scartati0
Arco non scelto
Arco scelto
Arco esaminato
Percorso alla meta
Che cosa stai osservando?
Dijkstra risolve un problema di percorsi. Prim e Kruskal risolvono invece il problema dell’albero di copertura minimo: i loro archi possono differire, ma il peso totale minimo coincide. Il disegno segue posizioni geometriche; i pesi degli archi sono assegnati a caso e non sono distanze sullo schermo.