Caminos Mínimos, Algoritmo Dijkstra en Java 8 - NetBeans IDE

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 (distancias entre nodos) 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. (Fuente Wikipedia).

Muchas veces tenemos que tomar desiciones como por ejemplo como Llegar  desde un punto de una ciudad hasta otro por el camino más corto, o en el caso de la informática en Aplicaciones para :

- Encaminamiento de paquetes por los routers: En un momento dado, un mensaje puede tardar cierta cantidad de tiempo en atravesar cada línea (por ejemplo, por efectos de congestión). En este caso, tenemos una red con dos nodos especiales, el de inicio y el de llegada. Los pesos de las aristas serían los costes. El objetivo del algoritmo es encontrar un camino entre estos dos nodos cuyo coste total sea el mínimo.

- Aplicaciones para Sistemas de información geográficos: extracción de características curvilíneas de imágenes usando técnicas de minimización del camino.

- Reconocimiento de lenguaje hablado: Se puede construir un grafo cuyos vértices correspondan a palabras posibles y las aristas unan palabras que pueden ir colocadas al lado de las otras. Si el peso de las aristas corresponde a la probabilidad de que estén así colocadas, el camino más corto en el grafo será la mejor interpretación de la frase.

- Enrutamiento de aviones y tráfico aéreo.

- Tratamiento de imágenes médicas.

Desarrolle la aplicación con Netbeans, puedes descargar el código fuente del siguiente enlace:

https://drive.google.com/file/d/10j9LFkoUdvCPyJ9DbIHyoJaRC9DSK97J/view?usp=sharing

Figura 1: Aplicación en java, muestra el camino más corto de Tumbes a Tacna.

Funcionamiento

- Para crear vértice o nodo (Punto de coordenadas en el plano) se hace con click izquierdo sobre la superficie, luego aparecerá un mensaje pidiéndote un nombre, se recomienda primero dibujar todos los nodos para después unirlos creando sus aristas respectivas.

- Para crear aristas con sus respectivos pesos o distancias, hacer click izquierdo sobre el primer nodo o vértice y después click izquierdo con el nodo o vértice que queremos unir, luego nos pedirá el peso o distancia entre ambos e ingresamos un número que deberá ser un entero positivo.

-Acabando de dibujar todos los nodos  y unirlos con sus aristas respectivas, podemos ya conocer la ruta más corta entre dos nodos distantes mediante el algoritmo de Dijkstra, para esto hacemos click derecho sobre el primer nodo y luego click derecho sobre el segundo nodo.


Saludos Imperio.