Hola a todos 

Hace poco que programo en Java, pero ya había programado en otros lenguajes.
Querría que me orientaran un poco sobre cómo resolver un ejercicio cómo el siguiente:


Había pensado en un grafo no dirigido y etiquetado.
Pero no sé cómo guardar los datos de ciudades y distancias.
Podría utilizar una estructura donde las columnas fuesen nodos (ciudades) y las filas destinos y guardar el número de kilómetros.

Pero después de guardar los datos no sabría como conseguir un recorrido de una ciudad origen a una destino (evitando bucles es decir de ciudadA a ciudadB a ciudadA a CiudadB cuando quiero ir de CiudadA a ciudadC).

Existe el backtracking pero quiero algo más simple. También hay el algoritmo de Dijkstra que me daría el camino óptimo entre dos ciudades, pero preferiría hacer algo más simple aunque no obtuviese el camino óptimo, sólo un camino por muy largo que fuese. Usando recursividad por ejemplo.

• Citar
  PD: Sólo quiero ideas, gracias 

Gracias por tu respuesta. He buscado los 4 tipos por internet y lo haré con una Lista de Adjacencias. 

I sobre el algoritmo de Dijkstra me parece bien