Imprimir Página - Urgente, proyecto, Dijkstra, ruta más corta xc

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.

Código:

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

Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: axel19 en 3 Junio 2018, 23:20 pm