¿Qué es dijkstra?
Algoritmo de Dijkstra
El algoritmo de Dijkstra, nombrado así por el científico de la computación Edsger W. Dijkstra, es un algoritmo para encontrar los caminos más cortos desde un nodo de origen hasta todos los demás nodos en un grafo con pesos no negativos en las aristas. Es ampliamente utilizado en enrutamiento de redes, sistemas de mapas y otras aplicaciones donde es necesario encontrar las rutas más eficientes.
Principios clave:
- Grafos ponderados: Opera en grafos donde cada arista tiene un peso asociado (generalmente representando la distancia o el costo).
- No negativo: El algoritmo de Dijkstra requiere que los pesos de las aristas sean no negativos.
- Nodo de origen: Calcula la distancia más corta desde un nodo de origen específico a todos los demás nodos del grafo.
- Greedy: Es un algoritmo greedy, lo que significa que toma la decisión óptima en cada paso local con la esperanza de encontrar la solución óptima global.
Proceso general:
- Inicialización: Se asigna una distancia tentativa infinita a todos los nodos excepto al nodo de origen, al cual se le asigna una distancia de 0.
- Conjunto de nodos no visitados: Se crea un conjunto de todos los nodos no visitados.
- Iteración: Mientras el conjunto de nodos no visitados no esté vacío:
- Se selecciona el nodo no visitado con la menor distancia tentativa actual.
- Para cada vecino del nodo seleccionado:
- Se calcula la distancia tentativa a través del nodo seleccionado.
- Si esta distancia tentativa es menor que la distancia tentativa actual del vecino, se actualiza la distancia tentativa del vecino.
- Se marca el nodo seleccionado como visitado (se elimina del conjunto de nodos no visitados).
Conceptos Importantes:
- Grafo Ponderado: Un grafo donde cada arista tiene un peso asignado.
- Distancia Más Corta: La ruta con el menor costo total (suma de pesos de las aristas) entre dos nodos.
- Nodo Origen: El nodo desde el cual se calcula la distancia a todos los demás nodos.
- Complejidad Temporal: Depende de la implementación. Con una cola de prioridad (como un heap binario), la complejidad es O((|V|+|E|)log|V|), donde |V| es el número de nodos y |E| el número de aristas. Con una matriz de adyacencia, la complejidad es O(|V|^2).
- Limitaciones: No funciona correctamente con grafos que contienen aristas con pesos negativos. En esos casos, se deben utilizar otros algoritmos como el algoritmo de Bellman-Ford.