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

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  [Estructuras de Datos] Algoritmo de Prim y su ruta mas corta
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Estructuras de Datos] Algoritmo de Prim y su ruta mas corta  (Leído 5,881 veces)
Wacherax

Desconectado Desconectado

Mensajes: 5


Ver Perfil
[Estructuras de Datos] Algoritmo de Prim y su ruta mas corta
« en: 30 Octubre 2012, 19:17 pm »

Buenas, estoy haciendo el algoritmo de prim en java como trabajo, ya lo tengo casi terminado y en general no tengo mucho problema.

La cosa surge sobre que algoritmo creeis que deberia utilizar para recorrer el arbol resultante. Es decir, con prim obtendre un arbol, pero yo quiero llegar desde un punto del arbol a otro cualquiera utilizando el menor camino posible ( de coste)

Ejemplo de arbol
Código:
O111
 |
 O-O-O-O-O
 |            
 |            
 |
 O-O-O-O
       |
      O2222

Para grafos dirigidos utilizaria dijkstra y tan panchos, pero como es un grafo no dirigido, no se que algoritmo utilizar para recorrer el arbol de expansion minima

El tema es que no consigo que se de cuenta de que es hoja y que es nodo...etc

No os pido que me lo hagais, solo si conoceis un algoritmo que pueda hacerlo, porque por mucho qe busco no veo ninguno..., a lo mejor existe una modificacion de dijkstra que lo haga, peor no lo conozco

Saludos y aver si alguien se acuerda de estas nuestras amigas las estructuras...


« Última modificación: 30 Octubre 2012, 19:19 pm por Wacherax » En línea

[Case]


Desconectado Desconectado

Mensajes: 474



Ver Perfil WWW
Re: [Estructuras de Datos] Algoritmo de Prim y su ruta mas corta
« Respuesta #1 en: 31 Octubre 2012, 02:09 am »

No se si entendi bien, tu problema es que no sabes como reconocer cuando esta en una hoja o en un nodo que no sea hoja, no?

Eso se podria arreglar solamente agregandole un campo a cada nodo, tal que tenga si es una hoja o un nodo.


En línea

Wacherax

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: [Estructuras de Datos] Algoritmo de Prim y su ruta mas corta
« Respuesta #2 en: 31 Octubre 2012, 17:33 pm »

No utilizamos una clase para cada nodo, por lo que no peudo añadir campos diciendo si es nodo u hoja

El tema seria que el algoritmo se diese cuenta de que ha llegado a una hoja y marcase el nodo con un verctor de booleanos

Si esa hoja no es el final, la olvida y vuelve a buscar otro camino que llegue al final marcando los nodos que no produzcan caminos y demas.

Seria como ir eliminando tenctaculos hasta que solo quede el bueno
En línea

Oblivi0n


Desconectado Desconectado

Mensajes: 392

Odio las ranas.


Ver Perfil
Re: [Estructuras de Datos] Algoritmo de Prim y su ruta mas corta
« Respuesta #3 en: 2 Noviembre 2012, 13:40 pm »

No será alumno de la unviersidad de Oviedo no? xD jajaja, nos han mandado lo mismo.

Lo que tienes que hacer, una vez aplicado Prim obtienes una matriz de pesos del arbol generador minimo, a esa matriz de pesos le aplicas el algoritmo de Floyd-Warshall, el cual te dará 2 cosas, una matriz de pesos, y una matriz de caminos, con lo cual solo tienes que seguir esa matriz de caminos para llegar de un nodo a otro, e ir sumando los pesos

http://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall

También se puede hacer por Backtracking

http://es.wikipedia.org/wiki/Vuelta_atr%C3%A1s
En línea

Hadess_inf
Desesperado
Colaborador
***
Desconectado Desconectado

Mensajes: 2.048


Nueva Vida


Ver Perfil WWW
Re: [Estructuras de Datos] Algoritmo de Prim y su ruta mas corta
« Respuesta #4 en: 17 Noviembre 2012, 18:02 pm »

Esto me hace recordar al problema del SNAKE PIT, para resolver tienes que usar algoritmo de floyd-warshall pero haciendo un ajusto con pesos de valor alto.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
¿Para que son las estructuras de datos? ¿Que ventaja ofrecen? « 1 2 »
Programación C/C++
Aikanáro Anário 11 4,559 Último mensaje 4 Junio 2010, 00:55 am
por @synthesize
ADT estructuras de datos
Programación C/C++
do-while 4 7,209 Último mensaje 3 Julio 2010, 13:11 pm
por O-LLOS-O
Problemas con estructuras de datos en C#
.NET (C#, VB.NET, ASP)
dark_headhunter 5 4,426 Último mensaje 5 Junio 2011, 17:20 pm
por neoncyber
Obtener ruta más corta
Programación C/C++
amchacon 8 8,627 Último mensaje 15 Junio 2013, 21:07 pm
por amchacon
Urgente, proyecto, Dijkstra, ruta más corta xc
Programación C/C++
axel19 1 2,687 Último mensaje 4 Junio 2018, 18:42 pm
por SrMcLister
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines