[Ideas] Grafos y Caminos

[RON06]

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:

El usuario entra los siguientes datos (guardados en un fixero):
(ciudad ciudad distancia)

CiudadA CiudadC 30
CiudadC CiudadD 20
CiudadB CiudadD 10



Le pregunta al usuario que diga los nombres de la ciudad origen y ciudad destino.
Y muestra una ruta para ir de Origen a Destino (Puede ser óptima o no da igual)

ORIGEN: CiudadB
DESTINO: CiudadA

CiudadB
CiudadD 10Km
CiudadC 20Km
CiudadA 30Km

KM TOTALES: 60Km

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.

• PD: Sólo quiero ideas, gracias 

[[Case]]

Utiliza el algoritmo de Dijsktra, para representar gráficas existen 4 formas de representar Graficas; con Matriz de Adjacencias, Matriz de Incidencias, Lista de Adjacencias y Lista de Incidencias.

[RON06]

Utiliza el algoritmo de Dijsktra, para representar gráficas existen 4 formas de representar Graficas; con Matriz de Adjacencias, Matriz de Incidencias, Lista de Adjacencias y Lista de Incidencias.

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