[C]Calcolo cammino ottimo

[kalbiz]

Ciao a tutti, ho il seguente problema.
in un grafo i cui vertici, contengono le coordinate (x,y), devo trovare il percorso minimo a partire da un vertice per arrivare ad un'altro.
ho provato con varie versioni di BFS ma non riesco a farmi restituire il cammino minino.. individua semplicemente il cammino.
Ora tentavo con un approccio diverso, algo di dijkstra, ma non ho ul peso associato agli archi.
mi chiedevo quindi avendo come unico dato utilizzabile, la profondità del nodo rispetto alla radice, come posso individuare il cammino minimo ??? avevo pensato anche a un backtrack , ma prima di cominciare a scrivere volevo un parere ...
grazie a tutti
ciao

[Paulin]

Cosa intendi per cammino minimo? Il percorso minore che unisce tutti i vertici? Poi, è una spezzata?

[kalbiz]

si il cammino

(4,8)R||(5,8)R||(6,8)R
(4,7)R||(5,7)R||(6,7)R
(4,6)V||(5,6)V||(6,6)R
(4,5)V||(5,5)R||(6,5)R

rappresentando in questo modo la griglia , dove il Vertice è identicato dalla sue coordinate,e da un attributo colore, dovrei diciamo andare da il vertice (4,8) al (5,5) però supponendo di non potere attraversare i nodi di colore diverso dal nodo origine...
quindi un percorso

(4,8)R;(5,8)R;(6,8)R;(6,7)R;(6,6)R;(5,5)R;(6,5)R

molto schemattizzato in una griglia 3x3 ma dovrebbe funzionare così...

nella mia lista di adicenza per ogni vertice ci sono i nodi che hanno lo stesso colore e che sono in posizione

|
- 0 -
|

non riesco a generare il cammino per portarmi da A a B o almeno lo genero ma estraggo tutti i vertici dello stesso colore adiacenti fino ad arrivare al punto B .
ma è sbagliato ....

grazie

[kalbiz]

qualche idea ?
sto cercando per A* algo ... vediamo che viene fuori ?
che ne pensate ?