Urgente, proyecto, Dijkstra, ruta más corta xc

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

26 Abril 2024, 22:03 pm

Tema destacado: Estamos en la red social de Mastodon

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,767 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

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	5,947	17 Noviembre 2012, 18:02 pm por Hadess_inf
		Obtener ruta más corta Programación C/C++	amchacon	8	8,713	15 Junio 2013, 21:07 pm por amchacon
		AYUDA PROYECTO URGENTE Programación C/C++	RAFA001	3	2,193	22 Agosto 2013, 15:49 pm por WHK
		iniciar proceso sin ruta maximizado! y cerrarlo desde el proyecto Programación Visual Basic	StbanMC	2	1,994	22 Abril 2014, 02:00 am por abkanis
		iniciar proceso sin ruta maximizado! y cerrarlo desde el proyecto Programación General	StbanMC	2	2,145	18 Marzo 2014, 18:18 pm por StbanMC

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines