elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Urgente, proyecto, Dijkstra, ruta más corta xc
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Urgente, proyecto, Dijkstra, ruta más corta xc  (Leído 2,984 veces)
axel19

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Urgente, proyecto, Dijkstra, ruta más corta xc
« en: 3 Junio 2018, 23:20 pm »

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



En línea

SrMcLister

Desconectado Desconectado

Mensajes: 35



Ver Perfil
Re: Urgente, proyecto, Dijkstra, ruta más corta xc
« Respuesta #1 en: 4 Junio 2018, 18:42 pm »

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


En línea

Código
  1. return((u.areHappy() && u.knowIt()) ? u.clapYourHands() : u.goFuckYourself());
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Estructuras de Datos] Algoritmo de Prim y su ruta mas corta
Programación General
Wacherax 4 6,234 Último mensaje 17 Noviembre 2012, 18:02 pm
por Hadess_inf
Obtener ruta más corta
Programación C/C++
amchacon 8 9,011 Último mensaje 15 Junio 2013, 21:07 pm
por amchacon
AYUDA PROYECTO URGENTE
Programación C/C++
RAFA001 3 2,389 Último mensaje 22 Agosto 2013, 15:49 pm
por WHK
iniciar proceso sin ruta maximizado! y cerrarlo desde el proyecto
Programación Visual Basic
StbanMC 2 2,103 Último mensaje 22 Abril 2014, 02:00 am
por abkanis
iniciar proceso sin ruta maximizado! y cerrarlo desde el proyecto
Programación General
StbanMC 2 2,356 Último mensaje 18 Marzo 2014, 18:18 pm
por StbanMC
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines