El Algoritmo de Dijkstra es un algoritmo de búsqueda de grafos que resuelve el problema del camino más corto desde un nodo inicial a todos los demás nodos en un grafo con pesos no negativos en las aristas. En otras palabras, encuentra la ruta más barata entre dos puntos.
Aquí te explicamos el algoritmo paso a paso:
- Inicialización: Se asigna un valor de distancia inicial a cada nodo. Al nodo inicial se le asigna una distancia de 0, y a todos los demás nodos se les asigna infinito (∞). También se crea un conjunto de nodos no visitados. Ejemplo: Si el nodo inicial es 'A', d(A) = 0, d(B) = ∞, d(C) = ∞, etc.
- Selección del nodo actual: Se selecciona el nodo no visitado con la menor distancia actual. Este nodo se convierte en el nodo actual. Ejemplo: Si d(A) es la distancia más pequeña entre los nodos no visitados, 'A' se convierte en el nodo actual.
- Actualización de las distancias de los vecinos: Para cada vecino no visitado del nodo actual, se calcula la distancia a través del nodo actual. Si esta distancia es menor que la distancia actual del vecino, se actualiza la distancia del vecino. Ejemplo: Si 'B' es un vecino de 'A' y la distancia de 'A' a 'B' es 2, entonces d(B) se actualiza a d(A) + 2 = 2.
- Marcado del nodo como visitado: Después de actualizar las distancias de todos los vecinos del nodo actual, se marca el nodo actual como visitado. Ejemplo: 'A' ahora se marca como visitado.
- Repetición: Se repiten los pasos 2-4 hasta que todos los nodos hayan sido visitados o hasta que el nodo destino haya sido visitado.
Ejemplo Simplificado: Imagina un mapa con ciudades conectadas por carreteras con peajes (los pesos). Dijkstra te dice la ruta más barata para llegar a cualquier ciudad desde tu ciudad de partida.
Must Read
Usos Prácticos:
- Enrutamiento en redes: Los protocolos de enrutamiento, como OSPF, utilizan variaciones del algoritmo de Dijkstra para encontrar las rutas más cortas para el tráfico de red.
- Sistemas de navegación GPS: Los sistemas GPS utilizan el algoritmo de Dijkstra para calcular la ruta más rápida o más corta entre dos ubicaciones.
