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

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

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

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.