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).
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
Pagar codigo fuente
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"
Gracias, es lo que necesito, pero publica el codigo
ResponderBorrarMuy bueno y muy bonito, pero ayudaria mas si compartieras el codigo, está excelente, solo hace falta agregarle una funcionalidad especifica y seria perfecto.
ResponderBorrarSalu2
Claro, voy a buscar el codigo fuente, es que no se donde lo deje, y luego lo publicaré, estaré atento a dudas y sugerencias...
ResponderBorrarSi porfa el codigo es que lo necesito para un proyecto super urgente!!
ResponderBorrarSi me lo puedes enviar te lo agradecira inmensamente!!!
natica61@gmail.com
gracias!!
Hoy en la noche cuelgo el código fuente.
ResponderBorrarListo, 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.
ResponderBorrardonde esta el codigo fuente x fa
Borrargracias amigo
ResponderBorrarGracias sin lugar a duda tu trabajo es exelente, te deseo muchos exitos
ResponderBorrarGracias Jose Antonio
BorrarExelente, muy bonita interfaz y funcionamiento
ResponderBorrarExcelente Aporte, Muchas Gracias !! .. la andaba buscando
ResponderBorraruna pregunta como funciona ??
ResponderBorrarose 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
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.
Borrarpara 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.
Muchas gracias por tu aporte. Eres genial :D
ResponderBorrarooye para que sirve el dato del peso?? o.O
ResponderBorrarPeso 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.
Borrarhola 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
ResponderBorrarNo conozco tu codigo, tendria que verlo
BorrarMuyy bueno man gracias ....pero como veo el codigo ??nada mas eso y gracias
ResponderBorrarHay dos link, uno para el ejecutable y otro para el fuente, revisa
Borraroye una ves que lo ejecuto no puedo unir los puntos por medio de las arista que puedo a ser? de antemano gracias
ResponderBorrarComo tratas de unir los vertices?, lee las indicaciones de uso y me cuentas.
Borrarmuchas 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!
ResponderBorrarHola 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
ResponderBorrar/*
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
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
BorrarFernando, muy interesante tu aporte, estoy buscando la solución utilizando matrices de adyacencia, no se si es posible que me ayudes.
ResponderBorrarBuscando 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.
Saludos, es una sensacion agridulce con relacion a la copia de mi entraba, pues apesar que mi objetivo es compartir es honorable respetar autoria.
BorrarCon relacion a tu peticion es posible, siempre y cuando investigues y me hagas consultas concretas ya que dispongo de poco tiempo para investigar.
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
ResponderBorrarSaludos 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.
BorrarQue tal Fernando tengo una duda muy grande sera que me puede ayudar?
ResponderBorrarHola raul, creo que la duda es la misma que mandaste a mi correo.
BorrarCon 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é
:)
Este comentario ha sido eliminado por el autor.
ResponderBorrarHola, primero felicitarte por tu trabajo, esta muy interesante y completo.
ResponderBorrarSegundo quisiera preguntarte si conoces informacion o material para implementar este algoritmo en javascript o para dispositivos moviles.
Hola.
BorrarTodo 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!
Por favor sería de mucha utilidad si nos podría facilitar el Código Fuente
ResponderBorrarMuchas gracias
Mario, estaba haciendo unos ajustes, en unas horas estará nuevamente habilitado el link, disculpen las molestias :)
Borrarcobras por descargar el codigo fuente?
ResponderBorrarhttps://www.paypal.com/webapps/hermes?token=16P72404SN4158818&useraction=commit&rm=1&mfid=1588016084865_7217116d684ed
Borrarooi fiz o pagamento e nao recebi o codigo fonte
ResponderBorrarDeu certo recebi o codigo
BorrarCobra por descargar el codigo fuente?
ResponderBorrarHola pague los 4 dolares me podrian dar el acceso
ResponderBorrarEspero le sirva y saque provecho
BorrarPodrías facilitarme el código compa, me serviría de gran ayuda amigo! Lo necesito para aprobar una asignatura.
Borrarcuanto cuesta tu codigo fuente?
ResponderBorrar