elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Los 10 CVE más críticos (peligrosos) de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  [Ideas] Grafos y Caminos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Ideas] Grafos y Caminos  (Leído 2,247 veces)
RON06

Desconectado Desconectado

Mensajes: 32


Aprendiz


Ver Perfil
[Ideas] Grafos y Caminos
« 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.

  • Citar
    PD: Sólo quiero ideas, gracias  ;D


En línea

[Case]


Desconectado Desconectado

Mensajes: 474



Ver Perfil WWW
Re: [Ideas] Grafos y Caminos
« Respuesta #1 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.


En línea

RON06

Desconectado Desconectado

Mensajes: 32


Aprendiz


Ver Perfil
Re: [Ideas] Grafos y Caminos
« Respuesta #2 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 :)
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Grafos
Java
soser 1 2,542 Último mensaje 4 Noviembre 2010, 22:53 pm
por Debci
grafos
Programación General
kailon 3 2,583 Último mensaje 6 Junio 2011, 16:54 pm
por Valkyr
Diferentes caminos entre dos nodos en un grafo
Programación General
dark_headhunter 2 8,498 Último mensaje 14 Julio 2011, 05:01 am
por pucheto
todos los caminos de un grafo
Java
.rn3w. 1 2,093 Último mensaje 11 Junio 2014, 03:47 am
por Gh057
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines