miércoles, 30 de mayo de 2012

Implementacion en Java del Algoritmo de Dijkstra





Hoy trataré 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, como costumbre más abajo pueden descargar código fuente y ejecutable, adicional en ésta entrada podrán encontrar mi explicación gráfica y paso a paso del Algoritmo de Dijkstra en PDF para que puedan descargar a sus computadores.

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.




Algoritmo dijkstra
Clic aqui para descargar 
View more documents from Rey Salcedo

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.







37 comentarios:

  1. Gracias, es lo que necesito, pero publica el codigo

    ResponderEliminar
  2. Muy bueno y muy bonito, pero ayudaria mas si compartieras el codigo, está excelente, solo hace falta agregarle una funcionalidad especifica y seria perfecto.
    Salu2

    ResponderEliminar
  3. Claro, voy a buscar el codigo fuente, es que no se donde lo deje, y luego lo publicaré, estaré atento a dudas y sugerencias...

    ResponderEliminar
  4. Si porfa el codigo es que lo necesito para un proyecto super urgente!!

    Si me lo puedes enviar te lo agradecira inmensamente!!!

    natica61@gmail.com


    gracias!!

    ResponderEliminar
  5. Listo, lo prometido es deuda, acabo de agregar un link para la descarga del código fuente del programa, espero les guste y les sirva de ayuda.

    ResponderEliminar
  6. Gracias sin lugar a duda tu trabajo es exelente, te deseo muchos exitos

    ResponderEliminar
  7. Exelente, muy bonita interfaz y funcionamiento

    ResponderEliminar
  8. Excelente Aporte, Muchas Gracias !! .. la andaba buscando

    ResponderEliminar
  9. una pregunta como funciona ??
    ose mi pregunta es que hay que undirle para que detecte el camino mas corto y alumbre o cambie de color por los arcos ????
    hace eso ???
    Por favor responde la pregunta

    ResponderEliminar
    Respuestas
    1. Hola Sergio Marin, te recomiendo que maximices la aplicacion para trabajar mejor pues no hace repaint cuando cambias el tamaño de la ventana, eso seria una mejora.

      para crear un nodo haces clic izquierdo, te pedira un dato que no es mas que una etiqueta para el nodo.

      para crear las aristas le das clic izquerdo sobre los nodos que deseas unir con la arista, te pedira un numero que representa el peso.

      una vez tengas el grafo diseñado, haces clic derecho sobre el nodo inicial y luego sobre el final para que te indique el camino mas corto por distra.

      Me acabo de dar cuenta que se pierde algunas veces el grafo a la vista, pero es porque hay que llamar el metodo repaint por cada evento que pase sobre la ventana.

      Eliminar
  10. Muchas gracias por tu aporte. Eres genial :D

    ResponderEliminar
  11. ooye para que sirve el dato del peso?? o.O

    ResponderEliminar
    Respuestas
    1. Peso seria la distancia que por medio de una arista une a dos vértices, ejemplo: si dos ciudades a y b estan separadas por una distancia x, el valor de x seria el peso.

      Eliminar
  12. hola saludos, yo ya tengo el algoritmo de disjktra y me sale solo el resultado osea el peso total del camino entre dos vertices, lo que necesito ayuda para hacer que me muestre el recorrido del camino mas corto en una lista, tomando tu ejemplo de la pantalla seria asi:L = 13,1,2,9,4,11 el problema es que no se en que momento cargar el vetice a la lista. espero que me puedas ayudar att: franklin

    ResponderEliminar
  13. Muyy bueno man gracias ....pero como veo el codigo ??nada mas eso y gracias

    ResponderEliminar
  14. oye una ves que lo ejecuto no puedo unir los puntos por medio de las arista que puedo a ser? de antemano gracias

    ResponderEliminar
    Respuestas
    1. Como tratas de unir los vertices?, lee las indicaciones de uso y me cuentas.

      Eliminar
  15. muchas graciias amigo, el profe de seguro me pone la participacion! ya que no sabe ni como explicarlo, muy sencillo su uso y el codigo entendible! gracias!

    ResponderEliminar
  16. Hola oye una preguntota, la verdad va estar algo tonta al inicio del la ejecucion del programa se tiene q meter el ejemplo de input, bueno esto
    /*
    EJEMPLO DE INPUT
    5 9
    1 2 7
    1 4 2
    2 3 1
    2 4 2
    3 5 4
    4 2 3
    4 3 8
    4 5 5
    5 3 5
    1
    */

    Me podrias decir como lo sacas, el algoritmo de dijkstra ya habia tenido la fortuna de verlo pero no recuerdo como se saca ese input, no se si es el peso del camino q trazas al ir cada nodo... crees q pudieras explicarmelo brevemente, espero q mi pregunta no t confunda
    En serio t lo agradeceria mucho

    ResponderEliminar
    Respuestas
    1. la fila y columna de números asumo que representa de alguna forma un grafo; pero la interpretación no creo que se ciña a algún patrón o estándar; si es un trabajo puesto por algún maestro o profesor, es el quien debe explicarte la interpretación del input... yo con gusto te puedo ayudar con la implementacion

      Eliminar
  17. Fernando, muy interesante tu aporte, estoy buscando la solución utilizando matrices de adyacencia, no se si es posible que me ayudes.

    Buscando en Internet, encontré a alguien que tiene tu mismo código publicado bajo su nombre, revisa:

    http://incanato.site90.com/index.php/codigos/java/12-caminos-minimos-algoritmo-dijkstra-en-java

    Saludos.

    ResponderEliminar
    Respuestas
    1. Saludos, es una sensacion agridulce con relacion a la copia de mi entraba, pues apesar que mi objetivo es compartir es honorable respetar autoria.

      Con relacion a tu peticion es posible, siempre y cuando investigues y me hagas consultas concretas ya que dispongo de poco tiempo para investigar.

      Eliminar
  18. hola amigo, disculpa la molestia, solo quisiera saber en como elimino un punto cuando lo ponga por error para no tener que reiniciar la aplicacion

    ResponderEliminar
    Respuestas
    1. Saludos Francisco, sí más recuerdo en el evento clic sobre el panel está involucrado un método que recibe por parámetro las coordenadas del lugar donde se hizo clic, sí en dichas coordenadas existe un nodo éste método retorna un objeto de dicho nodo, prueba poniéndolo a apuntar a nulo (nodo = null) y luego refresca el panel... No lo he probado, inténtalo y me comentas.

      Eliminar
  19. Que tal Fernando tengo una duda muy grande sera que me puede ayudar?

    ResponderEliminar
    Respuestas
    1. Hola raul, creo que la duda es la misma que mandaste a mi correo.

      Con relación a lo de tiempo, en grafo cuando se habla de manera de peso es un término genérico, pero en realidad puede ser cualquier cosa como por ejemplo, dificultad, distancia, costo, tiempo, ect.

      para tomar el grafo de manera predeterminada de un archivo de texto usando mi código debes empezar creando el grafo partiendo de los nodos teniendo en cuenta sus coordenadas xy luego creas las aristas teniendo en cuenta coordenadas xy inicio y xy fin donde ambas debe coincidir con dos nodos que previamente creaste y que serán unidos, además incluirás el peso (en tu caso el tiempo)

      - En la linea 180 de la clase Gui esta como crear nodos
      - De la linea 171 a la 177 de la clase Gui esta como crear aristas

      el archivo de texto se me ocurre asi:

      nodo1;12;10
      nodo2;12;40
      nodo3;20;40
      arista1;12;10;12;40;7
      arista2;12;40;20;40;5
      arista3;20;40;12;10;7

      eso te debe dar algo así como un triangulo el último número en las arista sería el peso (tiempo)

      por último recuerda que las coordenadas en el jPanel se incrementa para x de izquierda a derecha y para 'y' de arriba a abajo así: http://escarbandocodigo.files.wordpress.com/2010/03/ejexna.png?w=698

      Cacharea y me muestras como vas y con gusto te ayudaré

      :)

      Eliminar
  20. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  21. Hola, primero felicitarte por tu trabajo, esta muy interesante y completo.
    Segundo quisiera preguntarte si conoces informacion o material para implementar este algoritmo en javascript o para dispositivos moviles.

    ResponderEliminar
    Respuestas
    1. Hola.

      Todo consiste en comprender como funciona el algoritmo de Dijkstra y dominar conceptos intermedio de un lenguaje de programación que desees usar, no use librería especial, todo surgió de una buena explicación de una colega, dicha explicación la plasme en esta entrada 'http://usandojava.blogspot.com/search/label/Dijkstra'

      ¡Animo!

      Eliminar
  22. Por favor sería de mucha utilidad si nos podría facilitar el Código Fuente

    Muchas gracias

    ResponderEliminar
    Respuestas
    1. Mario, estaba haciendo unos ajustes, en unas horas estará nuevamente habilitado el link, disculpen las molestias :)

      Eliminar

Entrada destacada

Matriz de adyacencia para un grafo

"La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias."; aunque pa...