Giorno, ho provato a risolvere questo esercizio con l’algoritmo di Dijkstra ma non mi è riuscito, per caso c’è qualche procedimento più complicato? Mi particolare ho visto questo video qui Algoritmo di Dijkstra - YouTube
Beh non ho visto quel video ma penso abbia spiegato che Dijkstra funziona con dei pesi sugli archi, il fatto che qua i “pesi” siano sui nodi dovrebbe già destare qualche sospetto. In secondo luogo Dijkstra è usato per trovare la distanza minima tra due nodi in un grafo pesato, qua la richiesta è tutt’altra cosa, chiede il valore minimo che rispetti le varie condizioni. In genere questo tipo di esercizi della fase scolastica si risolve a occhio visto che i dati sono pochi e il cervello riesce ad “analizzare” il grafo ad occhio, sicuramente c’è anche un qualche algoritmo che risolve il problema ma pretendere di trovarlo al volo e poi applicarlo come se si fosse un computer penso sia una strada più lunga del necessario. Vai a occhio e trova la soluzione, semmai prova anche in due tre modi diversi e prendi il minimo che riesci a trovare.
L’algoritmo di Dijkstra come è già stato detto serve per vedere la distanza minima tra 2 nodi.
Il problema ti chiede altro.
Ciò che ti chiede è un “minimum spanning tree”, che detto in termini umani, sarebbe quell’insieme di archi che ti permette di collegare ogni nodo a tutti gli altri (direttamente o indirettamente), ma come dice “minimum”, ogni arco ha un peso.
Quindi per trovare la soluzione devi trovare sempre quell’insieme di archi ma che abbia peso totale (la somma del peso di ogni arco selezionato) minimo.
Credo che questo breve video possa aiutarti molto:
Kruskal’s algorithm
Ho individuato la soluzione con delle prove, ma ho provato il tuo algoritmo e non mi ha aiutato, perché è un algoritmo basato sui pesi negli archi. Non c’è un algoritmo che può risolvere questo esercizio con dei nodi pesati?