Grafo cammino minimo privo di pesi sugli archi

[valeriAsus]

Salve dato un grafo non orientato(rappresentato con la matrice di adiacenza),privo di nodi isolati e privo di pesi o distanze sugli archi,vi è qualche algoritmo noto per trovare il cammino minimo? perchè dando un occhiata veloce ho visto che quello di Dijkstra o Kruskal si basa sui pesi sugli archi...

[progAnd]

Credo basti una visita in profondità oppure in ampiezza; comunque quando non hai pesi sugli archi è come se avessi peso 1 su tutti gli archi

Ciao

[valeriAsus]

Salve dovrei fare questo esercizio:

Dovrei calcolare il numero di spostamenti minimi di un cavallo(pedina che si muove ad L come gli scacchi)su una matrice(scacchiera) per raggiungere un determinato punto P(cella).Cioè dato il cavallo posizionato in una cella qualsiasi 'P1' e data una cella di arrivo qualsiasi 'P2': qual'è il numero minimo di spostamenti da fare per spostare il cavallo da P1-->P2??

Io ho pensato di far corrispondere ogni cella della scacchiera ad un nodo di un grafo,per poter rappresentare la matrice di adiacenza,cosi so(se mAd[i][j]==true)per ogni cella della scacchiera dove si può spostare il cavallo.
Es
n=3
Scacchiera[n][n]={ 0 1 2
3 4 5
6 7 8
}
k=n*n
mAd[k][k]

nodi 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 1 0 1 0
1
2
3
4
5
6
7
8

//giusto per capirsi la prima riga indica che se il cavallo fosse al nodo 0, rappresentante la cella della scacchiera [0][0] si può spostare al nodo 5(Scacchiera[1][2]) o al 7(Scacchiera[2][1]) e cosi via considerando 5 ecc. o 7 ecc.

Il mio problema ora è l'algoritmo per trovare il cammino minimo per andare da P1 a P2 che risulterebbe molto complesso e incasinato nel considerare tutti i casi, tenendo conto di tutti i nodi percorsi ... non essendo riuscito nemmeno a trovare un modo per associare i pesi agli archi sempre rappresentando il problema,in modo da poter applicare kruscal o djktra o un altro algoritmo noto : chiedo umilmente aiuto, un piccolo consiglio per sbloccarmi confused:

[alka]

Originariamente inviato da valeriAsus
Salve dovrei fare questo esercizio

Siccome il problema è del tutto simile a quello precedentemente aperto, ho unito le discussioni.