Título: Matriz de distancias y Dijkstra Publicado por: xiruko en 9 Diciembre 2015, 05:26 am Hola,
estoy tratando de resolver un ejercicio de encontrar el camino más corto entre varios nodos y he pensado en hacerlo con el algoritmo de Dijkstra. El problema es que no sé como construir la matriz de distancias entre los distintos nodos. Como entrada me llega una matriz de carácteres, donde cada carácter representa algo: O O O N O X O X N X O X O X S X O -> Camino libre X -> Obstáculo S -> Nodo inicial N -> Nodos por los que tengo que pasar El tablero en este caso es 4x4 pero puede ser de cualquier dimensión hasta 100. Así que bueno... Alguien sabe algún método eficiente para construir la matriz de distancias entre los distintos nodos? Gracias! Título: Re: Matriz de distancias y Dijkstra Publicado por: SnzCeb en 12 Diciembre 2015, 13:38 pm Antes de nada, buscas hacerlo de un nodo a los demás únicamente, ¿De qué naturaleza son los grafos con los que vas a tratar? (Densos, dispersos . ..) ¿Hay caminos negativos?
|