miércoles, 30 de mayo de 2012

Implementacion en Java del Algoritmo de Dijkstra

Ejecutable al final de la pagina.



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.


-------------------------------------------------------------------------------------------------------------------
Saludos a todos.

Estoy agregándole algunas mejoras al programa, les mando un adelanto.