Algoritmo de Dijkstra
Última actualización
El algoritmo de Dijkstra encuentra el camino más corto desde un nodo origen hasta todos los demás nodos de un grafo con pesos de arista no negativos. Mantiene una distancia tentativa para cada nodo, fija repetidamente el nodo no fijado con la menor distancia tentativa y relaja sus aristas, actualizando la distancia de un vecino cada vez que se encuentra una ruta más corta a través del nodo actual. Pulsa reproducir arriba para ver cómo bajan las distancias a medida que se fija cada nodo.
La idea clave es voraz: una vez que se elige el nodo no fijado más cercano, su distancia es definitiva, porque cualquier otra ruta hacia él tendría que pasar por un nodo que ya está más lejos. Con una cola de prioridad basada en montículo binario, Dijkstra se ejecuta en tiempo O((V + E) log V). Requiere pesos no negativos: usa Bellman-Ford si las aristas pueden ser negativas.
Complejidad temporal y espacial
| Implementación | Complejidad | Notas |
|---|---|---|
| Montículo binario | O((V + E) log V) | La opción común y práctica |
| Barrido de array | O(V²) | Más simple; adecuado para grafos densos |
| Espacio | O(V) | Distancias + cola de prioridad |
| Requiere | Pesos no negativos | Las aristas negativas rompen la elección voraz |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Fija la distancia del origen en 0 y todas las demás en infinito. |
| 2 | Elige el nodo no fijado con la menor distancia tentativa. |
| 3 | Márcalo como fijado: su distancia más corta ya es definitiva. |
| 4 | Para cada vecino, calcula distancia-a-través-del-actual + peso de la arista. |
| 5 | Si es menor que la distancia actual del vecino, relájala. |
| 6 | Repite hasta fijar todos los nodos alcanzables. |
Ejemplo resuelto
Caminos más cortos desde el origen A en el grafo con aristas A-B=4, A-C=1, C-B=2, C-D=5, B-D=1:
| Paso | Fijar | Distancias | Acción |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | Inicializa: origen A=0, todos los demás infinito. |
| 1 | A (0) | B=4, C=1, D=∞ | Relaja las aristas desde A: fija B=4, C=1. |
| 2 | C (1) | B=3, D=6 | A través de C: B=1+2=3 mejora 4; D=1+5=6. |
| 3 | B (3) | D=4 | A través de B: D=3+1=4 mejora 6. |
| 4 | D (4) | A=0, C=1, B=3, D=4 | Fija D; no queda nada por relajar. Listo. |
Cuándo usar el algoritmo de Dijkstra
| Úsalo cuando | Evítalo cuando |
|---|---|
| Todos los pesos de arista son no negativos | Cualquier arista puede ser negativa: usa Bellman-Ford |
| Necesitas los caminos más cortos desde un origen a todos los nodos | Necesitas caminos más cortos entre todos los pares: Floyd-Warshall es más simple |
| El grafo es ponderado y quieres distancias exactas | El grafo no es ponderado: un BFS simple es más rápido y sencillo |
| Dispones de un buen montículo o cola de prioridad | Quieres llegar rápido a un único destino con una heurística: usa A* |
Código de Dijkstra's Algorithm
Una implementación limpia y ejecutable de Dijkstra's Algorithm en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Dijkstra's Algorithm en Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")Código de Dijkstra's Algorithm en JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));Código de Dijkstra's Algorithm en Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}Código de Dijkstra's Algorithm en C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}Código de Dijkstra's Algorithm en C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}Preguntas frecuentes sobre el algoritmo de Dijkstra
¿Cuál es la complejidad temporal del algoritmo de Dijkstra?
O((V + E) log V). Una versión simple que barre un array buscando el mínimo en cada paso es O(V²), que en realidad puede ser más rápida en grafos densos. Ambas usan espacio O(V).¿Por qué Dijkstra no funciona con pesos de arista negativos?
Dijkstra supone que, una vez que fija el nodo no fijado más cercano, esa distancia es definitiva. Una arista negativa podría crear después un camino más corto hacia un nodo ya fijado, rompiendo esa suposición. Para grafos con pesos negativos, usa el algoritmo de Bellman-Ford.
¿Cuál es la diferencia entre Dijkstra y BFS?
BFS encuentra los caminos más cortos contando aristas (cada peso de arista es efectivamente 1), usando una cola simple. Dijkstra generaliza esto a grafos ponderados expandiendo siempre el nodo con la menor distancia total, usando una cola de prioridad. En un grafo no ponderado ambos producen los mismos caminos.
¿Cuál es la diferencia entre Dijkstra y la búsqueda A*?
A* es Dijkstra más una heurística que estima la distancia restante hasta un destino, de modo que dirige la búsqueda hacia esa meta en lugar de expandirse uniformemente en todas direcciones. Cuando la heurística es cero, A* se reduce exactamente a Dijkstra. Usa A* cuando tienes un único destino y una buena heurística admisible; usa Dijkstra cuando necesitas distancias a todos los nodos.
¿Cuándo debería usar Dijkstra en lugar de Bellman-Ford?
O((V + E) log V) frente a O(V·E) de Bellman-Ford. Elige Bellman-Ford solo cuando las aristas pueden ser negativas o necesitas detectar ciclos negativos. En grafos no negativos Dijkstra casi siempre es la mejor opción.¿Puede Dijkstra volver a visitar un nodo después de fijarlo?
No: una vez que un nodo se fija, su distancia es definitiva y nunca se vuelve a relajar. Un error común en las implementaciones con montículo es dejar entradas obsoletas en la cola de prioridad después de que mejora la distancia de un nodo; debes ignorar un nodo extraído si ya está fijado (su distancia extraída supera la distancia registrada). Olvidar esta comprobación sigue dando respuestas correctas, pero desperdicia trabajo.
Recursos relacionados
Más visualizaciones
