[C] Cammino minimo tra 2 nodi

[metteus]

Ciao a tutti

ho un problema:
ho un albero Red black contenente biglie di colori diversi e uguali....
ogni biglia ha un campo con le adiacenze alle altre biglie secondo regole prestabilite. ogni biglia ha coordinate x,y e colore....

come faccio a trovare il percoso minimo tra una biglia e un altra passando per il minor numero di cambi di colore ?
cioè io posso avere anche un percorso lunghissimo ma se sto sempre nello stesso colore è meglio di uno cortissimo che pero cambia colere 2 o piu volte ... non so se avete capito il problema

che algoritmoo posso usare ?

thx

[Manbearpig]

Potresti forse usare Dijkstra adattandolo alla tua situazione, ad esempio prendendo come peso di un arco 1 se questo comporta un cambio di colore, 0 altrimenti.

[metteus]

Originariamente inviato da Manbearpig

Potresti forse usare Dijkstra adattandolo alla tua situazione, ad esempio prendendo come peso di un arco 1 se questo comporta un cambio di colore, 0 altrimenti.

cioè come funzionerebbe questo algoritmo ?

perche per il cammino omogeneo , cioè all'interno di biglie adiacenti dello stesso colore ho usato una visita in ampiezza, ma per questo variabile non so come comportarmi

grazie

[gugoXX]

Originariamente inviato da Manbearpig

Potresti forse usare Dijkstra adattandolo alla tua situazione, ad esempio prendendo come peso di un arco 1 se questo comporta un cambio di colore, 0 altrimenti.

Quoto Manbearpig.
E' proprio Dijkstra, ed hai il risultato ottimo.
Come fare ad implementarlo dipende da tantissime cose. Innanzitutto dovresti studiare l'algoritmo.

[metteus]

Originariamente inviato da gugoXX

Quoto Manbearpig.
E' proprio Dijkstra, ed hai il risultato ottimo.
Come fare ad implementarlo dipende da tantissime cose. Innanzitutto dovresti studiare l'algoritmo.

quello che non riesco a capire è come pesare i lati con 0 e 1 ,,,

[Manbearpig]

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

[metteus]

no dijlstra non funziona, ha provato un mio amico... ha detto che non trova il cammino minimo -.-
uffa....
non so proprio come far

[gugoXX]

Boh. Secondo me si puo' fare.
Trasformi l'albero delle adiacenze nella matrice completa delle adiacenze e sopra ci applici Dijkstra.

La matrice delle adiacenze dovresti sapere cosa e'.
Ogni colonna e' associata ad una biglia.
Ogni riga e' associata ad una biglia.
Ogni incrocio e' la distanza tra 2 biglie, che puo' valere
- infinito, se le due biglie non sono connesse
- 1 se le due biglie sono connesse ed hanno colore diverso
- 0 se le due biglie sono connesse ed hanno colore uguale

[cionci]

Concordo e dovrebbe dare l'ottimo.

[clasprea]

Originariamente inviato da metteus

no dijlstra non funziona, ha provato un mio amico... ha detto che non trova il cammino minimo -.-
uffa....
non so proprio come far

Guarda misa che è impossibile, sarà solo questione di capire come pesare gli archi, comunque su wikipedia è spiegato abbastanza bene, se ancora non ti sei documentato ti consiglio di leggerlo: http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

d'oh, mi sono accorta ora che era già stata linkata wikipedia ENG... torno a dormire va!