how implement dijkstra s algorithm java
Este tutorial explica cómo implementar el algoritmo de Dijkstra en Java para encontrar las rutas más cortas en un gráfico o árbol con la ayuda de ejemplos:
En nuestro tutorial anterior sobre gráficos en Java, vimos que los gráficos se utilizan para encontrar la ruta más corta entre los nodos, además de otras aplicaciones.
Para encontrar la ruta más corta entre dos nodos de un gráfico, generalmente empleamos un algoritmo conocido como ' Algoritmo de Dijkstra ”. Este algoritmo sigue siendo el algoritmo más utilizado para encontrar las rutas más cortas en un gráfico o un árbol.
=> Consulte TODOS los tutoriales de Java aquí
Lo que vas a aprender:
Algoritmo de Dijkstra en Java
Dado un gráfico ponderado y un vértice inicial (fuente) en el gráfico, el algoritmo de Dijkstra se utiliza para encontrar la distancia más corta desde el nodo fuente a todos los demás nodos del gráfico.
Como resultado de la ejecución del algoritmo de Dijkstra en un gráfico, obtenemos el árbol de ruta más corto (SPT) con el vértice fuente como raíz.
En el algoritmo de Dijkstra, mantenemos dos conjuntos o listas. Uno contiene los vértices que forman parte del árbol de ruta más corta (SPT) y el otro contiene los vértices que se están evaluando para incluirlos en SPT. Por lo tanto, para cada iteración, encontramos un vértice de la segunda lista que tiene la ruta más corta.
El pseudocódigo para el algoritmo de ruta más corta de Dijkstra se da a continuación.
pasando matrices a métodos en java
Pseudocódigo
A continuación se muestra el pseudocódigo de este algoritmo.
|_+_|Tomemos ahora un gráfico de muestra e ilustremos el algoritmo de ruta más corta de Dijkstra .
Inicialmente, el conjunto de SPT (Shortest Path Tree) se establece en infinito.
Comencemos con el vértice 0. Entonces, para empezar, colocamos el vértice 0 en sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
A continuación, con el vértice 0 en sptSet, exploraremos sus vecinos. Los vértices 1 y 2 son dos nodos adyacentes de 0 con distancia 2 y 1 respectivamente.
En la figura anterior, también hemos actualizado cada vértice adyacente (1 y 2) con su distancia respectiva desde el vértice fuente 0. Ahora vemos que el vértice 2 tiene una distancia mínima. A continuación, agregamos el vértice 2 al sptSet. Además, exploramos los vecinos del vértice 2.
Ahora buscamos el vértice con distancia mínima y los que no están en spt. Elegimos el vértice 1 con distancia 2.
Como vemos en la figura anterior, de todos los nodos adyacentes de 2, 0 y 1 ya están en sptSet, por lo que los ignoramos. De los nodos adyacentes 5 y 3, 5 tienen el menor costo. Así que lo agregamos al sptSet y exploramos sus nodos adyacentes.
En la figura anterior, vemos que excepto los nodos 3 y 4, todos los demás nodos están en sptSet. De 3 y 4, el nodo 3 tiene el menor costo. Así que lo pusimos en sptSet.
Como se muestra arriba, ahora solo nos queda un vértice, es decir, 4 y su distancia desde el nodo raíz es 16. Finalmente, lo colocamos en sptSet para obtener el sptSet = {0, 2, 1, 5, 3, 4} final que nos da la distancia de cada vértice desde el nodo fuente 0.
Implementación del algoritmo de Dijkstra en Java
La implementación del algoritmo de ruta más corta de Dijkstra en Java se puede lograr de dos formas. Podemos usar colas de prioridad y lista de adyacencia o podemos usar matrices y matrices de adyacencia.
En esta sección, veremos ambas implementaciones.
Usar una cola de prioridad
En esta implementación, usamos la cola de prioridad para almacenar los vértices con la distancia más corta. El gráfico se define mediante la lista de adyacencia. A continuación se muestra un programa de muestra.
|_+_|Producción:
Uso de la matriz de adyacencia
En este enfoque, usamos la matriz de adyacencia para representar el gráfico. Para spt set usamos matrices.
El siguiente programa muestra esta implementación.
|_+_|Producción:
Preguntas frecuentes
P # 1) ¿Dijkstra funciona para gráficos no dirigidos?
Responder: Si el gráfico está dirigido o no dirigido, no importa en el caso del algoritmo de Dijkstra. Este algoritmo se ocupa solo de los vértices del gráfico y los pesos.
P # 2) ¿Cuál es la complejidad temporal del algoritmo de Dijkstra?
Responder: La complejidad temporal del algoritmo de Dijkstra es O (V 2). Cuando se implementa con la cola de prioridad mínima, la complejidad de tiempo de este algoritmo se reduce a O (V + E l o g V).
P # 3) ¿Es Dijkstra un algoritmo codicioso?
Responder: Sí, Dijkstra es un algoritmo codicioso. De forma similar al algoritmo de Prim de encontrar el árbol de expansión mínimo (MST), estos algoritmos también comienzan desde un vértice raíz y siempre eligen el vértice más óptimo con la ruta mínima.
P # 4) ¿Es Dijkstra DFS o BFS?
Responder: No es ninguno. Pero como el algoritmo de Dijkstra utiliza una cola de prioridad para su implementación, puede verse como algo cercano a BFS.
P # 5) ¿Dónde se usa el algoritmo de Dijkstra?
Responder: Se utiliza principalmente en protocolos de enrutamiento, ya que ayuda a encontrar la ruta más corta de un nodo a otro.
Conclusión
En este tutorial, hemos discutido el algoritmo de Dijkstra. Usamos este algoritmo para encontrar la ruta más corta desde el nodo raíz a los otros nodos en el gráfico o árbol.
Por lo general, implementamos el algoritmo de Dijkstra utilizando una cola de prioridad, ya que tenemos que encontrar la ruta mínima. También podemos implementar este algoritmo usando la matriz de adyacencia. Hemos discutido estos dos enfoques en este tutorial.
Esperamos que este tutorial le resulte útil.
=> Visite aquí para ver la serie de formación de Java para todos
Lectura recomendada
- Algoritmo de búsqueda binaria en Java: implementación y ejemplos
- Clasificación de burbujas en Java: ejemplos de código y algoritmos de clasificación de Java
- Orden de inserción en Java: algoritmo de ordenación de inserción y ejemplos
- Orden de selección en Java: algoritmo de ordenación de selección y ejemplos
- QuickSort en Java - Algoritmo, ilustración e implementación
- Tutorial de JAVA para principiantes: más de 100 tutoriales prácticos en vídeo de Java
- Tutorial de reflexión de Java con ejemplos
- Matriz irregular en Java - Tutorial con ejemplos