DOMANDA Algoritmo Dijkstra

[MPG]

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.

 

[_Achille]

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)

 

[MPG]

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)

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.

 

[_Achille]

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.

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]

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.

SI intendevo dire perchè è 6?

 

[_Achille]

SI intendevo dire perchè è 6?

Devi arrivare a 4 e sei a 0. Hai un arco che congiunge 0 con 4 di lunghezza 6. 4 da 0 è raggiungibile quindi in 6 unità

 

[rodhellas]

https://it.wikipedia.org/wiki/Ricerca_in_ampiezza

 

[DispatchCode]

@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).