Hola querida comunidad
Necesito hacer un proyecto de una aplicación de medios de transporte
Ya tengo todo salvo en el algoritmo que utilizare
Debo utilizar el Algoritmo de Dijkstra en lenguaje C o C++ para encontrar las rutas más cortas, sin embargo el que tengo me genera errores y en verdad me urge
Me genera rutas pero en ocasiones no son las más cortas, sigo trabajando en ello pero neta me urge tener correcto el algoritmo
Si alguien tiene un código del algoritmo de Dijkstra, me lo podrían proporcionar???
De antemano muchas gracias y excelente día
Buenas axel19.
Para realizar el algoritmo de Dijsktra lo eficiente sería usar una programación dinamica, recursiva o iterativa lo que mejor te convenga, ya que recursivamente y mediante ese tipo de programación, estarás guardando en un array de n posiciones las aristas ya recorridas por las cuales no debes volver a pasar.
Llevar a cabo la implementación de este algoritmo es sencillo usando una cola de prioridad.. aqui te dejo el pseudocodigo.
DIJKSTRA (Grafo G, nodo_fuente s)
para u ∈ V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
visto[u] = false
distancia[s] = 0
adicionar (cola, (s, distancia[s]))
mientras que cola no es vacía hacer
u = extraer_mínimo(cola)
visto[u] = true
para todos v ∈ adyacencia[u] hacer
si distancia[v] > distancia[u] + peso (u, v) hacer
distancia[v] = distancia[u] + peso (u, v)
padre[v] = u
adicionar(cola,(v, distancia[v]))
Si no sabes usar colas de prioridad, la complejidad aumenta algo más.
Tienes ejemplos de este algoritmo resuelto en Pseudocodigo, Java y C++ en la Wikipedia; adjunto link: https://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#Otra_versi%C3%B3n_en_C++_del_algoritmo_de_Dijkstra
Un saludo y suerte!!