Título: [Ideas] Grafos y Caminos Publicado por: RON06 en 25 Febrero 2012, 21:02 pm Hola a todos ;D
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: Citar 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.
Título: Re: [Ideas] Grafos y Caminos Publicado por: [Case] en 26 Febrero 2012, 10:24 am 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.
Título: Re: [Ideas] Grafos y Caminos Publicado por: RON06 en 26 Febrero 2012, 12:40 pm 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. :D I sobre el algoritmo de Dijkstra me parece bien :) |