Duda de que algoritmo me conviene más
Hola! Estoy programando en C++ un grafo para que me permita generar el camino mínimo entre dos puntos dados, el arco que une los nodos establece la distancia euclidea. Sé que hay algoritmos como el Dijkstra que lo realiza... Pero, la forma en la que yo tengo organizado el grafo/arbol es que el nodo inicial va a ser siempre mi punto de partida y las hojas mi punto final, teniendo ya prefijado esta estructura, mi pregunta es si no seria más conveniente realizar un recorrido en profundidad e ir almacenandome el coste de ese camino, en el momento que yo este visitando un arco y el coste ya sea mayor que el que yo tengo como máximo entonces realizo una poda de esa rama y ya no sigo por ahí.. En resumen yo creo que seria más efectivo un recorrido en profundidad haciendo backtraking que implementar el algoritmo de Dijkstra pero no sé si esta decisión es la acertada o no. ¿Alguien me puede ayudar por favor?
1 Respuesta
Respuesta de harkonnen24
1
A ver, un árbol es un grafo pero no todos los grafos son arboles ... es decir un árbol es un tipo particular de grafo sin ciclos. De manera que si lo que utilizas es un árbol, que cuadra más de la manera que hablas (punto de partida(raíz), punto final (hojas)) no tiene sentido el utilizar un algoritmo de búsqueda de camino único entre dos puntos, ya que solo hay una posibilidad de ir de un punto a otro.
Aquí lo que buscaríamos seria cual es la rama de mayor/menor peso o mayor/menor profundidad. Para esto debes de adecuar un algoritmo de recorrido de arboles y como indicas ir guardando el el valor del peso de la rama o la profunidad.
Pero si lo que tenemos es un grafo propiamente dicho, es decir existen ciclos ( que no parece por tu explicación ) entonces pasamos a hablar de algoritmos de camino mínimo, donde Dijkstra es el más conocido, que es el que se aprende en Mates, pero no el más eficiente, ademas si fuera un algoritmo de este tipo habría que tener en cuenta si los pesos pueden ser negativos ...
Aquí lo que buscaríamos seria cual es la rama de mayor/menor peso o mayor/menor profundidad. Para esto debes de adecuar un algoritmo de recorrido de arboles y como indicas ir guardando el el valor del peso de la rama o la profunidad.
Pero si lo que tenemos es un grafo propiamente dicho, es decir existen ciclos ( que no parece por tu explicación ) entonces pasamos a hablar de algoritmos de camino mínimo, donde Dijkstra es el más conocido, que es el que se aprende en Mates, pero no el más eficiente, ademas si fuera un algoritmo de este tipo habría que tener en cuenta si los pesos pueden ser negativos ...
