Nodi in un grafo

[Caroncino]

Salve,

Mi trovo ad avere un grafo strutturato in modo tale che ogni nodo ha un solo arco entrante ed al più due archi uscenti. Inoltre il peso di ogni arco dipende dai precedenti due nodi. Quindi il grafo ha più nodi uguali in quanto due nodi possono essere uniti da un arco che ha peso diverso a seconda del nodo che precede i due in questione.
La domanda è se è lecito avere un grafo così strutturato e se in un grafo possso esserci più nodi uguali.

[Cheguevilla]

Cosa intendi quando dici che il grafo ha più nodi uguali?
Cosa intendi per "nodi uguali"?
Se ogni nodo ha un solo arco uscente, il peso di ogni arco è univocamente identificabile, se è questo che vuoi dire.
Se ho capito bene le condizioni poste, il grafo è lecito.
Per quanto riguarda i "nodi uguali", direi che dipende dal significato che assume il grafo in questione ma, dal punto di vista puramente geometrico, i nodi possono essere tutti uguali.

[Caroncino]

Prendi in esame il gioco del quindici (il gioco in cui si devono mettere in ordine i numeri dall'1 al 15 avendo un solo posto libero per muovere le varie caselle) e mettiamo che io debba portare la casella 1 al suo posto. Io devo costruire un grafo che mi permetta di esplicitare tutti i percorsi che la casella 1 può percorrere per raggiungere la sua esatta posizione (nel mio caso la strategia usata permette alla casella 1 di spostarsi solo in quelle posizioni che la avvicinano alla sua posizione esatta e quindi non avrò cicli e percorsi che si ripetono, ovvero il mio grafo non avrà archi che tornano indietro). Sotto queste condizioni io ho che i nodi mi rappresentano le celle in cui posso spostare la casella 1, mentre i pesi degli archi indicano quanti spostamenti di caselle in totale devo fare per spostare la mia casella 1 da una cella ad un'altra adiacente (in questo caso ho che il peso di ogni arco può essere 3 o 5). Quindi se io costruisco un grafo, questo dovrò avere nodi uguali, cioè diversi nodi che indicano la stessa cella, perchè il peso dell'arco che va da un nodo ad un altro può avere due valori diversi (3 o 5) a seconda di dove si trova la casella vuota per gli spostamenti e quindi a seconda di dove si trovava la casella 1 prima di giungere al primo dei due nodi in quesione.
Non so se sono stato chiaro nella spiegazione

E' giusto costruire il mio grafo in questo modo? Ci sono altri modi per costruirlo? In alternativa posso ricorerre ad un albero?

[Cheguevilla]

Formalmente è giusto e direi che si giunge anche ad una soluzione.
Intanto penso a delle alternative.
Un grafo costruito con queste regole è un albero.

[Caroncino]

Ma un albero può avere i rami pesati? In ogni caso posso adottare come algoritmo di ricerca Dijkstra?
Grazie mille per le risposte

[Cheguevilla]

Certo che un albero può avere rami pesati.
Esistono algoritmi per trovare, dato un grafo connesso, l'albero con il minor peso.
Per quanto riguarda il tuo problema, of course, l'algoritmo di Dijkstra può essere utilizzato tranquillamente.

[Caroncino]

Ok, grazie ancora e se hai novità fammi sapere.

[Caroncino]

riguardo all'algoritmo di ricerca posso usare il greedy? Provando sperimentalmente sono quasi sicuro che è adatto al mio caso, ma come posso giustificare il suo uso?