[Estructuras de Datos] Algoritmo de Prim y su ruta mas corta

[Wacherax]

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 [Seleccionar] Expandir


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...

[[Case]]

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.

[Wacherax]

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

[Oblivi0n]

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

[Hadess_inf]

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.