Complejidad Temporal
O(V²)
El algoritmo de Dijkstra encuentra el camino más corto desde un nodo origen a todos los demás nodos en un grafo ponderado con pesos no negativos.
Cómo funciona:
1. Inicializar distancias: origen = 0, todos los demás = ∞
2. Marcar todos los nodos como no visitados
3. Seleccionar el nodo no visitado con la menor distancia
4. Para cada vecino no visitado, calcular la distancia tentativa
5. Si la nueva distancia es menor, actualizarla
6. Marcar el nodo actual como visitado
7. Repetir hasta que todos los nodos estén visitados
Complejidad Temporal:
O(V²) con arreglo simple
O((V + E) log V) con min-heap binario
Complejidad Espacial: O(V)
Aplicaciones:
- Navegación GPS y planificación de rutas
- Protocolos de enrutamiento de red (OSPF)
- Encontrar caminos más cortos en mapas
- Análisis de redes sociales
El algoritmo de Dijkstra es uno de los algoritmos de grafos más importantes. Garantiza soluciones óptimas para grafos con pesos no negativos.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Algoritmo de Dijkstra?
- El algoritmo de Dijkstra encuentra el camino más corto desde un nodo origen a todos los demás nodos en un grafo ponderado con pesos no negativos.
- ¿Cuál es la complejidad de Algoritmo de Dijkstra?
- Tiempo (promedio): O(V²) · Espacio: O(V)
- ¿Para quién es este visualizador de Algoritmo de Dijkstra?
- La visualización de Algoritmo de Dijkstra está pensada para nivel avanzado, dentro de la categoría Grafos. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Algoritmo de Dijkstra?
- En la misma categoría (Grafos) puedes explorar: Breadth-First Search, Depth-First Search, Prim's Algorithm. Todos tienen visualización interactiva.