DOMANDA Algoritmo Dijkstra

Pubblicità
M

MPG

Utente Attivo
Messaggi
566
Reazioni
4
Punteggio
55
Scusate stavo guardando la spiegazione. Sotto il disegno dice che a partire dal nodo 0 assegnerebbe al nodo 4 un cammino minimo di peso 6 (si parla di "visita in ampiezza" di cui non so il significato) e nel caso migliore 4 . QUest'ultimo lo comprendo passando dal nodo 0-1-4= peso 4 , ma il primo con 6 non lo capisco che cammino di nodi è? Vedo quell'arco da 0 a 4 con peso 6 ma se passassi per i nodi 0-2-3 e 4 il totale del peso è 5.. Ci è stato accennato questo algoritmo e dato da studiare per la verifica qualcuno mi spiegarmi il mio dubbio? Grazie.
 

Allegati

  • Dijstra.webp
    Dijstra.webp
    176.3 KB · Visualizzazioni: 81
Ultima modifica:
Devi leggerla tutta la frase. 4 non è il caso migliore, bensì il caso migliore fino alla seconda iterazione di un algoritmo che visita il grafo. Il caso migliore ha infatti lunghezza 3 (0->1->3->4)
 
_Achille ha detto:
Devi leggerla tutta la frase. 4 non è il caso migliore, bensì il caso migliore fino alla seconda iterazione di un algoritmo che visita il grafo. Il caso migliore ha infatti lunghezza 3 (0->1->3->4)
Clicca per espandere...

Ma come è intesa la "visita in ampiezza" che da 6 ? perche' 0->2->3->4>5 avrebbe peso 6 mentre in figura c'è quel segno ad arco con il 6 tra il nodo 0 e il 4.
 
MPG ha detto:
Ma come è intesa la "visita in ampiezza" che da 6 ? perche' 0->2->3->4>5 avrebbe peso 6 mentre in figura c'è quel segno ad arco con il 6 tra il nodo 0 e il 4.
Clicca per espandere...
Non si capisce quello che vuoi sapere.

Il 6 esce dall’arco che congiunge lo 0 al 4. Perciò in primo luogo sembra che sia la soluzione migliore.
 
@MPG dovresti vedere i grafi e la ricerca in un altro modo, da come secondo me li stai immaginando (questo per comprendere ad esempio i pesi sugli archi). Immagina ogni nodo come una città, ed i pesi sugli archi come i km che separano le città.
Il peso non lo metti tu, è parte del problema da risolvere (ovvero trovare un cammino minimo).
 
Pubblicità
Pubblicità
Indietro
Top