Motivation
Lección 2 de 9 del curso Algoritmo de Dijkstra - Algoritmos de grafos de Coddy.
Dijkstra hace crecer un conjunto de vértices cuya distancia más corta ya es conocida. Siempre finaliza el vértice más cercano que aún no ha sido finalizado, y luego lo utiliza para mejorar (relajar) las distancias a sus vecinos.
¿Por qué aprender Dijkstra?
- En todas partes: Enrutamiento GPS, enrutamiento de paquetes de red y cualquier búsqueda de rutas de costo mínimo.
- Voraz que funciona: un ejemplo claro de una elección voraz que demostrablemente da el óptimo, siempre que los pesos no sean negativos.
- Fundamento: su idea de relajación reaparece en A* y otros algoritmos de camino más corto.
Importante: Dijkstra asume que no hay pesos negativos. Las aristas negativas requieren Bellman-Ford, el siguiente curso.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
