[Algoritmi]Cammini minimi Dijkstra

[piedeamaro_2]

salve, ho un dubbio nel crea la tabella per riportare i costi dei cammini tra i nodi di un grafo.

Un dato cammino, ha un costo tipo (4,B), dovuto all'esplorazione del nodo in uso, ed esso è il costo più basso al momento.
Se cerco il cammino minimo, il nodo successivo che vado ad esplorare ha un costo uguale ma dato da un percorso diverso tipo: (4,D) devo sostituirlo al valore precedente (4,B) o lascio il vecchio?

Se trovo un cammino a costo più alto tipo: (5,D) non devo sostituirlo vero?

ciao

[marx1]

Il cammino che ha lo stesso costo non c'è bisogno di sostituirlo.
Quello di costo più alto non va sostituito visto che sei interessato alla ricerca del cammino minimo da un vertice sorgente agli altri vertici.
ciao

[Ext3rmin4tor]

In realtà sostituire o meno un cammino di costo uguale non varia il risultato, ovvero ottieni alla fine sempre un cammino minimo, il fatto è che l'algoritmo sviluppato nei due modi diversi può dare come risultato due cammini minimi diversi, ma ciò non importa perché alla fine a te interessa UN cammino minimo qualunque.