Ejecutable al final de la pagina.
Tambien te puede interesar "Explicación gráfica sobre el Algoritmo de Dijkstra","Aplicacion de mapas, usando grafos y Dijkstra"
Saludos,
Saludos,
Hoy
tratare el tema Algoritmo de Dijkstra, tema perteneciente a
la teoría de grafos, así que para entender esto debemos repasar primero
que es un grafo y los términos que giran alrededor es este.
Definición de Algoritmo de Dijkstra: El
algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es
un algoritmo para la determinación del camino más corto dado un vértice
origen al resto de vértices en un grafo con pesos en cada arista. Su
nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez
en 1959.
La
idea subyacente en este algoritmo consiste en ir explorando todos los
caminos más cortos que parten del vértice origen y que llevan a todos
los demás vértices; cuando se obtiene el camino más corto desde el
vértice origen, al resto de vértices que componen el grafo, el algoritmo
se detiene. (Tomado de Wikipedia).
En
palabras propias puedo decir que Algoritmo de Dijkstra nos sirve para
determinar el camino mas corto entre dos nodos dados que pertenecen a un
grafo.
-----------------------------------------------------------------
Me
tome la tarea de crear una modesta aplicación que me
permita graficar un grafo con pesos y determinar la ruta mas corta entre
dos nodos dados, he aqui un patallazo:
El funcionamiento es bastante simple:
- Para crear nodo o vértice con clic izquierdo sobre la superficie, luego te pedirá un nombre.
-
Para crear aristas, hacer clic izquierdo sobre los nodos o vértices que
deseamos unir, luego nos pedirá el peso que debera ser un entero
positivo.
-
Para conocer la ruta mas corta por Dijkstra, hacemos clic derecho sobre
el primer nodo y luego clic derecho sobre el segundo nodo.
Adjunto ejecutable, y como siempre esperando serles de utilidad.
Tambien te puede interesar "Explicación gráfica sobre el Algoritmo de Dijkstra"
-------------------------------------------------------------------------------------------------------------------
Saludos a todos.
Estoy agregándole algunas mejoras al programa, les mando un adelanto.
No hay comentarios:
Publicar un comentario