Algoritmo de Dijkstra para niños
Datos para niños Algoritmo de Dijkstra |
||
|---|---|---|
 Ejecución del algoritmo de Dijkstra
|
||
| Tipo | Algoritmo de búsqueda | |
| Problema que resuelve | Problema del camino más corto | |
| Estructura de datos | Grafo | |
| Creador | Edsger Dijkstra | |
| Fecha | 1959 | |
| Clase de complejidad | P | |
| Tiempo de ejecución | ||
| Peor caso |  |
|
El algoritmo de Dijkstra es un método muy inteligente para encontrar el camino más corto entre un punto de inicio y todos los demás puntos en un mapa o red. Imagina que tienes un mapa con ciudades y carreteras, y cada carretera tiene un "peso" o costo (por ejemplo, el tiempo que tardas en recorrerla). Este algoritmo te ayuda a encontrar la ruta más rápida o más barata.
Fue creado por un científico de la computación llamado Edsger Dijkstra en los Países Bajos en 1956 y lo publicó en 1959. Es muy útil en muchas áreas, como la navegación GPS o la planificación de redes.
La idea principal es ir explorando poco a poco todos los caminos posibles desde el punto de partida. El algoritmo siempre elige el camino más corto que ha encontrado hasta ese momento. Se detiene cuando ha descubierto el camino más corto desde el inicio a todos los demás puntos. Sin embargo, no funciona si hay "costos negativos" en las carreteras, como si viajar por una carretera te hiciera ganar tiempo en lugar de perderlo.
Contenido
¿Cómo funciona el algoritmo de Dijkstra?
Para entender el algoritmo, piensa en un grafo como un mapa. Los "nodos" o "vértices" son las ciudades, y las "aristas" son las carreteras que las conectan. Cada carretera tiene un "peso", que es su distancia o costo.
Pasos para encontrar el camino más corto
Aquí te explicamos cómo funciona el algoritmo paso a paso:
- Preparación:
- Imagina que tienes una lista de todas las ciudades y sus distancias desde tu punto de partida. Al principio, no conoces la distancia a la mayoría de las ciudades, así que las marcas como "infinito" (muy lejos).
- La distancia desde tu ciudad de partida hasta ella misma es 0.
- Marca todas las ciudades como "no visitadas".
- Comienza a explorar:
- Elige tu ciudad de partida como la "ciudad actual".
- Visita a los vecinos:
- Mira todas las ciudades que están conectadas directamente a tu "ciudad actual" y que aún no has visitado.
- Para cada una de estas ciudades vecinas, calcula una "distancia tentativa". Esta distancia es la que ya tienes para tu "ciudad actual" más el costo de la carretera que va de tu "ciudad actual" a la ciudad vecina.
- Si esta "distancia tentativa" es menor que la distancia que tenías registrada para esa ciudad vecina, ¡actualiza su distancia en tu lista! Esto significa que has encontrado una ruta más corta para llegar a ella.
- Marca como visitado:
- Una vez que has revisado todos los vecinos de tu "ciudad actual", la marcas como "visitada". Esto significa que ya has encontrado el camino más corto para llegar a ella desde el inicio.
- Elige la siguiente ciudad:
- Ahora, de todas las ciudades que aún no has visitado, elige aquella que tenga la distancia más corta registrada hasta el momento. Esa será tu nueva "ciudad actual".
- Repite los pasos 3 y 4 hasta que todas las ciudades hayan sido visitadas o hasta que no queden ciudades accesibles.
Al final, tendrás la distancia más corta desde tu punto de partida a todas las demás ciudades.
¿Qué tan rápido es el algoritmo de Dijkstra?
La velocidad de un algoritmo se llama "complejidad". El algoritmo de Dijkstra es bastante eficiente. Su velocidad depende de cuántas ciudades y carreteras tenga tu mapa.
- Si el mapa es pequeño, el algoritmo es muy rápido.
- En mapas más grandes, su velocidad puede variar. Los expertos en computación han encontrado formas de hacerlo aún más rápido usando estructuras de datos especiales, como las "colas de prioridad".
En resumen, el algoritmo de Dijkstra es una herramienta poderosa para encontrar las rutas más eficientes en redes de todo tipo.
Pseudocódigo (versión simplificada)
El pseudocódigo es como una receta escrita para un programa de computadora. Aquí te mostramos una versión sencilla del algoritmo:
DIJKSTRA (Grafo G, nodo_inicio s)
- Para cada nodo u en el grafo G:
- Establece la distancia de u como INFINITO (muy grande).
- Establece el "padre" de u como NULO (no hay camino aún).
- Marca u como NO VISITADO.
- Establece la distancia del nodo_inicio s como 0.
- Añade el nodo_inicio s a una lista de "nodos por visitar" (con su distancia 0).
- Mientras la lista de "nodos por visitar" no esté vacía:
- Toma el nodo u de la lista que tenga la distancia más pequeña.
- Marca u como VISITADO.
- Para cada nodo v que sea vecino de u:
- Si v no ha sido VISITADO:
- Si la distancia de v es mayor que (distancia de u + costo de la carretera entre u y v):
- Si v no ha sido VISITADO:
* Actualiza la distancia de v a (distancia de u + costo de la carretera entre u y v). * Establece el "padre" de v como u (para recordar el camino). * Añade v a la lista de "nodos por visitar" (con su nueva distancia).
Galería de imágenes
-
Ejecución del algoritmo de Dijkstra
Véase también
En inglés: Dijkstra's algorithm Facts for Kids
- Anexo:Ejemplo de Algoritmo de Dijkstra
- Algoritmo de Bellman-Ford
- Algoritmo de Prim
