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

 

 


Tema destacado: Introducción a Git (Primera Parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Matriz de distancias y Dijkstra
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Matriz de distancias y Dijkstra  (Leído 1,605 veces)
xiruko


Desconectado Desconectado

Mensajes: 437


Ver Perfil
Matriz de distancias y Dijkstra
« 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!


« Última modificación: 9 Diciembre 2015, 05:34 am por xiruko » En línea

SnzCeb

Desconectado Desconectado

Mensajes: 10


Ver Perfil
Re: Matriz de distancias y Dijkstra
« Respuesta #1 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? 


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Algoritmo de Dijkstra en Visual Basic
Programación Visual Basic
laukibuk 4 11,901 Último mensaje 17 Enero 2008, 07:32 am
por cobein
Codigo Dijkstra en C
Programación C/C++
SLACE 3 11,667 Último mensaje 17 Febrero 2012, 03:18 am
por SLACE
Algoritmo para un ejercicio; ¿Doble dijkstra?
Programación General
astinx 2 2,431 Último mensaje 16 Febrero 2012, 19:27 pm
por astinx
Matriz mapa de distancias.
Programación C/C++
brunojuy 3 1,411 Último mensaje 11 Octubre 2012, 18:03 pm
por pasajero
Auxilio con ALGORITMO DE DIJKSTRA!!!!! :'c
Programación C/C++
axel19 1 1,106 Último mensaje 3 Junio 2018, 10:23 am
por MAFUS
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines