Algoritmo de Dijkstra
Matemáticas Computacionales
Aviso Importante
Contenido
Encontrando el Camino Más Corto
Imagina que necesitas viajar de Dublín a Cork. Hay muchas rutas posibles — algunas más rápidas, algunas más cortas, algunas más económicas en combustible. Este es un problema de búsqueda de caminos: dada una red de ubicaciones conectadas por carreteras, encontrar la "mejor" ruta de un punto a otro. "Mejor" puede significar menor tiempo, menor distancia, mayor ancho de banda o menor costo — todos estos son problemas de optimización.
Podemos modelar estas redes como grafos ponderados: las ubicaciones se convierten en nodos (también llamados vértices), las carreteras se convierten en aristas, y cada arista tiene un peso — un número que representa su costo (distancia, tiempo, etc.). Un algoritmo es simplemente una serie de instrucciones paso a paso para resolver un problema. El Algoritmo de Dijkstra (pronunciado "Dike-stra", en honor al científico de la computación holandés Edsger Dijkstra) es uno de los algoritmos más famosos para encontrar el camino más corto en un grafo ponderado.
El objetivo es simple: encontrar una secuencia de nodos conectando un nodo de origen a un nodo de destino que tenga el menor peso combinado de aristas. El enfoque de Dijkstra funciona explorando hacia afuera desde el nodo de origen, siempre eligiendo el vecino no visitado más cercano primero, y construyendo gradualmente una tabla de distancias más cortas conocidas. Cuando alcanza el destino, garantiza que el camino es óptimo.
¿Por Qué Necesitamos un Algoritmo?
El enfoque de fuerza bruta no escala
Prueba todos los caminos posibles de A a H, calcula el costo total de cada uno y elige el más corto.
| 7 nodes | Cientos de caminos |
| 100 nodes | Millones de caminos |
| 1,000 nodes | Más caminos que átomos en el universo |
Visita nodos de forma inteligente — siempre elige el nodo no visitado más cercano. Cada nodo se visita como máximo una vez.
| 7 nodes | 7 pasos |
| 100 nodes | ~100 pasos |
| 1,000 nodes | ~1.000 pasos |
Grafo Ponderado
El grafo que usaremos para rastrear el algoritmo de Dijkstra
Cada número en una arista representa el costo de viajar entre dos nodos
El Algoritmo
Cuatro pasos para encontrar el camino más corto
Paso 0 — Comenzar en el Nodo A
Inicializar distancias y comenzar
Paso 1 — Visitar el Nodo C (costo 1)
C tiene la menor distancia en la cola
Paso 2 — Visitar el Nodo B (costo 2)
B tiene la menor distancia entre los nodos no visitados
Paso 3 — Visitar el Nodo D (costo 3)
Los vecinos de D ya fueron visitados — sin actualizaciones
Pasos 4 y 5 — Visitar E (costo 5), luego F (costo 7)
Acercándose a H
Resultado — ¡Camino Más Corto Encontrado!
A → C → F → H con costo total 9
Ejemplo Resuelto 2 — Un Grafo Más Grande
Encontrando el camino más corto de S a T en un grafo de 7 nodos
Ejemplo Resuelto 2 — Recorrido Animado
Observa a Dijkstra encontrar el camino de S a T
Ejemplo Resuelto 2 — Recorrido por Columnas
Columnas paso a paso de S a T
Ejemplo Resuelto 3 — Encontrando Todos los Caminos Más Cortos
A veces el viaje importa más que el destino
Ejemplo Resuelto 3 — Ejecución Completa de Dijkstra
Encontrando los caminos más cortos de P a todos los nodos
| Destination | Shortest Distance | Path |
|---|---|---|
| Q | 1 | P → Q |
| R | 3 | P → Q → R |
| S | 6 | P → Q → R → S |
| T | 8 | P → Q → R → T |
| U | 7 | P → Q → R → S → U |
Ejemplo Resuelto 3 — Recorrido por Columnas
Columnas paso a paso de P a todos los nodos
Recorrido Paso a Paso
Ejecutando Dijkstra de A a H — siguiendo el algoritmo
Dijkstra vs A* — Comparación en Cuadrícula
Mismo mapa, mismo costo — pero mira cuántos nodos visita cada algoritmo
A* visitó 90 nodos. Dijkstra visitó 555 — más de 6 veces más. Video de Kevin Wang.
A* visitó 90 nodos. Dijkstra visitó 555 — más de 6 veces más. Video de Kevin Wang.
Dijkstra vs A* — Comparación en el Mundo Real
Observa a Dijkstra explorar cada calle de Roma antes de encontrar el camino
Dijkstra tardó 21:04 en encontrar el camino. A* encontró el mismo camino en solo 02:03. Video de Anthony Madorsky.
Dijkstra tardó 21:04 en encontrar el camino. A* encontró el mismo camino en solo 02:03. Video de Anthony Madorsky.
Dijkstra vs A* — Entendiendo la Diferencia
Dos algoritmos, un objetivo — pero estrategias muy diferentes
- •Explores nodes in ALL directions equally
- •Guaranteed to find the shortest path
- •No knowledge of where the target is
- •Like a ripple spreading in a pond
- •Visits many unnecessary nodes
- •Explores towards the target first
- •Also guaranteed shortest path (with admissible heuristic)
- •Uses a heuristic — estimated distance to target
- •Like following a compass towards your destination
- •Visits far fewer nodes
A* adds one extra piece of information: an estimate of how far each node is from the target. Instead of picking the node with the smallest distance from start (like Dijkstra), A* picks the node with the smallest distance from start + estimated distance to target. This simple addition dramatically reduces the number of nodes explored.
| Feature | Dijkstra | A* |
|---|---|---|
| Uses heuristic? | No | Yes |
| Finds shortest path? | Always | Yes (with admissible heuristic) |
| Speed | Slower (explores everything) | Faster (focused search) |
| Memory usage | Higher | Lower |
| Best for | All shortest paths from one source | Single source to single target |
| Used in | Network routing, database queries | GPS navigation, video games |
Aplicaciones en el Mundo Real
Donde los algoritmos de camino más corto impulsan nuestra vida diaria
Every time you ask Google Maps or Apple Maps for directions, a variant of Dijkstra’s algorithm runs on millions of road segments. The edges are roads, weights are travel times (updated in real-time with traffic data), and the algorithm finds the fastest route. Modern GPS uses A* with geographical distance as the heuristic.
When you send a message on WhatsApp, it travels through multiple routers to reach its destination. Protocols like OSPF (Open Shortest Path First) use Dijkstra’s algorithm to find the fastest path through the network. Each router is a node, each connection is an edge weighted by latency or bandwidth.
En juegos como Age of Empires, Civilization o cualquier juego de estrategia, las unidades necesitan navegar alrededor de obstáculos para llegar a su destino. A* es el algoritmo estándar de búsqueda de caminos en el desarrollo de juegos. Se ejecuta miles de veces por segundo para mover personajes, enemigos y NPCs por el mapa.
LinkedIn’s ‘degrees of connection’ and Facebook’s ‘People You May Know’ use graph algorithms to find short paths between users. The ‘six degrees of separation’ concept is essentially a shortest path problem on a social graph with billions of nodes.
Algoritmo de Dijkstra en Java
Usando una cola de prioridad para encontrar el camino más corto
import java.util.*; public class DijkstraAlgorithm { // Find shortest distances from start to all nodes public static int[] dijkstra(int[][] graph, int start) { int n = graph.length; int[] distances = new int[n]; boolean[] visited = new boolean[n]; // Initialise all distances to "infinity" Arrays.fill(distances, Integer.MAX_VALUE); distances[start] = 0; // Priority queue: {distance, node} PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); queue.offer(new int[]{0, start}); while (!queue.isEmpty()) { int[] current = queue.poll(); int dist = current[0], node = current[1]; if (visited[node]) continue; visited[node] = true; // Check all neighbours for (int next = 0; next < n; next++) { if (graph[node][next] > 0 && !visited[next]) { int newDist = dist + graph[node][next]; if (newDist < distances[next]) { distances[next] = newDist; queue.offer(new int[]{newDist, next}); } } } } return distances; } }
public class Main { public static void main(String[] args) { // Adjacency matrix — 0 means no direct connection // A B C D E F H int[][] graph = { {0, 2, 1, 0, 0, 0, 0}, // A {2, 0, 0, 1, 3, 0, 0}, // B {1, 0, 0, 3, 0, 6, 0}, // C {0, 1, 3, 0, 0, 0, 0}, // D {0, 3, 0, 0, 0, 5, 0}, // E {0, 0, 6, 0, 5, 0, 2}, // F {0, 0, 0, 0, 0, 2, 0} // H }; String[] nodes = {"A","B","C","D","E","F","H"}; int[] distances = DijkstraAlgorithm.dijkstra(graph, 0); // Print shortest distances from A for (int i = 0; i < nodes.length; i++) { System.out.println("A → " + nodes[i] + " = " + distances[i]); } // Output: A → H = 9 } }
Referencia Rápida
| Concepto | Notación | Significado |
|---|---|---|
| Nodo (Vértice) | A, B, C... | Un punto/ubicación en el grafo |
| Arista | A—B | Una conexión entre dos nodos |
| Peso | w(A,B) = 3 | El costo de recorrer una arista |
| Grafo Ponderado | G(V, E) | Un grafo donde cada arista tiene un peso |
| Matriz de Adyacencia | M[i][j] | Una tabla que almacena los pesos de las aristas entre todos los pares de nodos |
| Tabla de Distancias | d[v] | Rastrea la menor distancia conocida a cada nodo |
| Camino Más Corto | A → C → F → H | La secuencia de nodos con menor peso total |
| Cola de Prioridad | min-heap | Selecciona el nodo no visitado con la menor distancia |
Ejercicios Prácticos
Pon a prueba tu comprensión del Algoritmo de Dijkstra
¿Cuál es el costo total?
Muestra la tabla de distancias después de cada paso e identifica el camino más corto.
Encuentra el camino más corto de A a E. Muestra tu razonamiento en cada paso.
a) Ejecuta Dijkstra desde W para encontrar la menor distancia a cada tienda.
b) ¿Cuál es el camino más corto de W a S3?
c) Si la carretera W–S2 está cerrada por obras, ¿cuál es el nuevo camino más corto de W a S3?
int[][] graph = {
{0, 6, 0, 1, 0},
{6, 0, 5, 2, 2},
{0, 5, 0, 0, 5},
{1, 2, 0, 0, 1},
{0, 2, 5, 1, 0}
};a) ¿Qué distancia reporta Dijkstra como la más corta de A a C?
b) ¿Cuál es la distancia más corta REAL?
c) ¿Por qué falla Dijkstra?
d) Nombra un algoritmo que maneje pesos negativos.
Muestra tu razonamiento paso a paso.
Muestra cada paso del algoritmo e identifica el camino más corto.
Aristas: S–A(2), S–B(5), A–C(4), A–E(7), B–D(2), B–E(1), C–T(3), D–T(4), E–C(1), E–D(3). Muestra tu razonamiento completo.
Aristas: R1–R2(3), R1–R3(6), R2–R4(2), R2–R5(5), R3–R5(3), R3–R6(1), R4–R7(4), R5–R7(2), R5–R6(2), R6–R8(5), R7–R8(1). Muestra la tabla de distancias completa en cada paso.
Respuestas
| A | B | C | |
|---|---|---|---|
| A | 0 | 3 | 5 |
| B | 3 | 0 | 1 |
| C | 5 | 1 | 0 |
Parte a) Dijkstra desde W:
| Step | Current | W | S1 | S2 | S3 | S4 |
|---|---|---|---|---|---|---|
| 0 | W | 0 | 10 | 5 | ∞ | ∞ |
| 1 | S2 | 0 | 8 | 5 | 13 | 7 |
| 2 | S4 | 0 | 8 | 5 | 11 | 7 |
| 3 | S1 | 0 | 8 | 5 | 9 | 7 |
| 4 | S3 | 0 | 8 | 5 | 9 | 7 |
Distancias más cortas: S1=8, S2=5, S3=9, S4=7
Parte b) Camino más corto de W a S3:
W → S2 → S1 → S3, cost = 5 + 3 + 1 = 9
Parte c) W–S2 cerrada:
Sin la arista W–S2, el único camino a S1 es directo (costo 10). Luego S1→S3 = 1. Entonces W → S1 → S3, costo = 10 + 1 = 11.
| Step | Current | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 6 | ∞ | 1 | ∞ |
| 1 | 3 | 0 | 3 | ∞ | 1 | 2 |
| 2 | 4 | 0 | 3 | 7 | 1 | 2 |
Camino más corto: 0 → 3 → 4, costo = 2 (1 + 1). La matriz muestra que del nodo 0 al nodo 3 el peso es 1, y del nodo 3 al nodo 4 el peso es 1.
b) El camino más corto real es A→B→C = 5 + (−10) = −5.
c) Dijkstra falla porque finaliza C con distancia 2 antes de descubrir el camino más barato por B. Una vez que un nodo se marca como visitado, nunca se reconsidera — la suposición voraz ("la menor distancia es final") se rompe cuando existen pesos negativos, porque sumar un peso negativo puede hacer que un camino más largo sea más corto.
d) El algoritmo de Bellman-Ford maneja pesos negativos relajando TODAS las aristas V−1 veces, garantizando que se encuentren todos los caminos más cortos.
b) Más corto real: A→B→C = 1 + (−5) = −4.
c) Dijkstra marca C como visitado con distancia 4 antes de descubrir el camino por B. Una vez visitados, los nodos nunca se reconsideran — esta es la suposición fundamental que se rompe con pesos negativos.
d) El algoritmo de Bellman-Ford maneja pesos negativos relajando todas las aristas V−1 veces, garantizando que se encuentren todos los caminos más cortos.
Referencias
Fuentes utilizadas en la elaboración de este material
¡Feliz estudio!
Los algoritmos son la base de la resolución eficiente de problemas en computación