¿Qué es y para qué sirve el algoritmo Dijkstra?

Introducción

Algoritmos hay muchos, pero pocos son tan importantes y útiles como el algoritmo de Dijkstra. Si alguna vez has usado una aplicación de mapas para encontrar la ruta más rápida a tu destino, ya has aprovechado los conceptos detrás de este algoritmo, aunque no lo supieras.

Dijkstra es una de esas herramientas matemáticas que parecen complicadas al principio, pero tienen aplicaciones muy prácticas: navegación, redes, logística, videojuegos, sistemas de rutas y optimización de caminos en estructuras conectadas.

En este artículo te explico qué es el algoritmo de Dijkstra, cómo funciona y para qué se utiliza. La idea es desmenuzarlo paso a paso, con ejemplos claros y código en diferentes lenguajes.

¿Qué es el algoritmo de Dijkstra?

El algoritmo de Dijkstra es una técnica utilizada en informática y matemáticas para encontrar el camino más corto entre dos puntos dentro de un grafo.

Un grafo es una estructura formada por nodos, también llamados vértices, y conexiones entre ellos, llamadas aristas. Por ejemplo, un grafo puede representar un mapa de una ciudad, donde cada nodo es una intersección y cada arista representa una calle.

Contexto histórico: ¿quién fue Dijkstra?

El algoritmo lleva el nombre de Edsger W. Dijkstra, un científico de la computación de los Países Bajos que lo desarrolló en 1956. Dijkstra es considerado uno de los pioneros de la informática moderna, y su algoritmo sigue siendo uno de los más conocidos en ciencias de la computación.

Lo interesante es que fue diseñado en una época en la que las computadoras eran mucho menos potentes que hoy, lo que demuestra la elegancia de su propuesta: resolver un problema complejo con una lógica eficiente y ordenada.

Grafos, pesos y caminos

Dijkstra trabaja sobre grafos ponderados. Esto significa que cada conexión entre nodos tiene un peso o costo asociado. Ese peso puede representar distancia, tiempo, latencia, costo económico o cualquier medida que quieras minimizar.

El objetivo del algoritmo es encontrar el camino con menor costo total desde un nodo inicial hasta otro nodo, o incluso desde un nodo inicial hacia todos los demás nodos del grafo.

A---1---B
|       |
4       3
|       |
C---2---D

¿Para qué sirve el algoritmo de Dijkstra?

Dijkstra se utiliza principalmente para encontrar el camino más corto entre dos puntos en un grafo. Este tipo de problema aparece en muchas áreas: navegación, telecomunicaciones, logística, videojuegos, redes eléctricas y sistemas de planeación.

Navegación y mapas

Una de sus aplicaciones más claras está en los sistemas de navegación. Cuando una app de mapas calcula una ruta eficiente, evalúa posibles caminos entre dos puntos y busca minimizar una variable: distancia, tiempo estimado o costo del recorrido.

Redes de comunicación

En telecomunicaciones, el algoritmo puede ayudar a encontrar el camino más eficiente para enviar datos entre servidores, routers o nodos de red. En este contexto, el peso de cada conexión puede representar latencia, ancho de banda disponible o congestión.

Planificación de rutas y logística

En logística y transporte, Dijkstra puede ayudar a planear rutas más cortas o eficientes. Esto permite reducir tiempos de entrega, costos de traslado y consumo de recursos.

Videojuegos y sistemas interactivos

En videojuegos, los personajes o agentes pueden usar algoritmos de rutas para desplazarse en mapas, tableros o escenarios. Aunque en juegos suele usarse mucho A*, Dijkstra es una base conceptual muy importante para entender estos sistemas.

¿Cómo funciona el algoritmo de Dijkstra?

Dijkstra es un proceso sistemático. Parte de un nodo inicial, asigna distancias tentativas a todos los nodos y va actualizando esas distancias conforme encuentra rutas más cortas.

Paso 1: Inicialización

Primero se inicializan todos los nodos con distancia infinita, excepto el nodo inicial, que tiene distancia 0. También se marcan todos los nodos como no visitados.

Paso 2: Evaluación de vecinos

Después se selecciona el nodo no visitado con la distancia más pequeña y se evalúan sus vecinos. Si llegar a un vecino a través del nodo actual produce una distancia menor que la registrada, se actualiza.

Paso 3: Marcar el nodo como visitado

Cuando ya se evaluaron sus conexiones, el nodo actual se marca como visitado. Esto indica que ya se encontró la distancia más corta posible hacia ese nodo.

Paso 4: Repetir hasta completar

El algoritmo repite el proceso: seleccionar el nodo no visitado más cercano, evaluar vecinos, actualizar distancias y marcar como visitado. Al final, se obtiene la distancia mínima desde el nodo inicial hacia todos los demás nodos alcanzables.

Ejemplo en pseudocódigo

Una forma sencilla de entender Dijkstra es verlo como una rutina que mantiene una tabla de distancias y la va mejorando conforme explora el grafo.

function Dijkstra(grafo, nodoInicio):
    distancia[nodoInicio] = 0

    para cada nodo en grafo:
        si nodo != nodoInicio:
            distancia[nodo] = infinito
        anterior[nodo] = indefinido

    colaDeNodos = grafo.nodos

    mientras colaDeNodos no esté vacía:
        nodoActual = nodo con menor distancia en colaDeNodos
        eliminar nodoActual de colaDeNodos

        para cada vecino de nodoActual:
            ruta = distancia[nodoActual] + peso(nodoActual, vecino)

            si ruta < distancia[vecino]:
                distancia[vecino] = ruta
                anterior[vecino] = nodoActual

    retornar distancia, anterior

Este pseudocódigo muestra la idea central: conservar siempre la mejor distancia conocida y actualizarla si aparece una ruta más barata.

Implementación en Python

Python es uno de los lenguajes más usados para aprender algoritmos por su claridad. En este ejemplo usamos una cola de prioridad con heapq para seleccionar eficientemente el nodo con menor distancia.

import heapq

def dijkstra(grafo, inicio):
    distancias = {nodo: float("inf") for nodo in grafo}
    distancias[inicio] = 0

    anteriores = {}
    cola_prioridad = [(0, inicio)]

    while cola_prioridad:
        distancia_actual, nodo_actual = heapq.heappop(cola_prioridad)

        if distancia_actual > distancias[nodo_actual]:
            continue

        for vecino, peso in grafo[nodo_actual].items():
            distancia = distancia_actual + peso

            if distancia < distancias[vecino]:
                distancias[vecino] = distancia
                anteriores[vecino] = nodo_actual
                heapq.heappush(cola_prioridad, (distancia, vecino))

    return distancias, anteriores


grafo = {
    "A": {"B": 4, "C": 2},
    "B": {"A": 4, "D": 3, "E": 2},
    "C": {"A": 2, "D": 4},
    "D": {"B": 3, "C": 4, "E": 3},
    "E": {"B": 2, "D": 3}
}

distancias, anteriores = dijkstra(grafo, "A")

print("Distancias desde A:", distancias)
print("Camino anterior:", anteriores)

Implementación en JavaScript

En JavaScript también podemos implementar Dijkstra usando una estructura sencilla de cola de prioridad. Para proyectos grandes conviene usar una implementación más eficiente, pero esta versión es útil para entender la lógica.

class PriorityQueue {
    constructor() {
        this.values = [];
    }

    enqueue(node, priority) {
        this.values.push({ node, priority });
        this.values.sort((a, b) => a.priority - b.priority);
    }

    dequeue() {
        return this.values.shift();
    }

    isEmpty() {
        return this.values.length === 0;
    }
}

function dijkstra(graph, start) {
    const distances = {};
    const previous = {};
    const queue = new PriorityQueue();

    for (const node in graph) {
        distances[node] = Infinity;
        previous[node] = null;
    }

    distances[start] = 0;
    queue.enqueue(start, 0);

    while (!queue.isEmpty()) {
        const { node: currentNode } = queue.dequeue();

        for (const neighbor in graph[currentNode]) {
            const distance = distances[currentNode] + graph[currentNode][neighbor];

            if (distance < distances[neighbor]) {
                distances[neighbor] = distance;
                previous[neighbor] = currentNode;
                queue.enqueue(neighbor, distance);
            }
        }
    }

    return { distances, previous };
}

const graph = {
    A: { B: 4, C: 2 },
    B: { A: 4, D: 3, E: 2 },
    C: { A: 2, D: 4 },
    D: { B: 3, C: 4, E: 3 },
    E: { B: 2, D: 3 }
};

console.log(dijkstra(graph, "A"));

Implementación en C++

C++ es una buena opción cuando necesitas eficiencia. Aquí usamos priority_queue para mantener siempre al frente el nodo con menor distancia conocida.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>

using namespace std;

using Pair = pair<int, int>;
const int INF = numeric_limits<int>::max();

void dijkstra(unordered_map<int, vector<Pair>>& graph, int start) {
    unordered_map<int, int> distances;

    for (const auto& node : graph) {
        distances[node.first] = INF;
    }

    distances[start] = 0;

    priority_queue<Pair, vector<Pair>, greater<Pair>> queue;
    queue.push({0, start});

    while (!queue.empty()) {
        int currentDistance = queue.top().first;
        int currentNode = queue.top().second;
        queue.pop();

        if (currentDistance > distances[currentNode]) {
            continue;
        }

        for (const auto& neighbor : graph[currentNode]) {
            int nextNode = neighbor.first;
            int weight = neighbor.second;
            int distance = currentDistance + weight;

            if (distance < distances[nextNode]) {
                distances[nextNode] = distance;
                queue.push({distance, nextNode});
            }
        }
    }

    for (const auto& result : distances) {
        cout << "Distancia desde " << start
             << " hasta " << result.first
             << " es " << result.second << endl;
    }
}

int main() {
    unordered_map<int, vector<Pair>> graph;

    graph[1] = {{2, 4}, {3, 2}};
    graph[2] = {{1, 4}, {4, 3}, {5, 2}};
    graph[3] = {{1, 2}, {4, 4}};
    graph[4] = {{2, 3}, {3, 4}, {5, 3}};
    graph[5] = {{2, 2}, {4, 3}};

    dijkstra(graph, 1);

    return 0;
}

Conclusión

El algoritmo de Dijkstra es una herramienta fundamental en informática y matemáticas. Su propósito es claro: encontrar el camino más corto en un grafo minimizando el costo total del recorrido.

Aunque al principio puede parecer complejo, su lógica es bastante directa: partir desde un nodo, conservar la mejor distancia conocida, evaluar vecinos y actualizar rutas cuando aparece una opción más barata.

Dijkstra es un excelente punto de partida para entender problemas de rutas, grafos, optimización y estructuras de datos. Después de comprenderlo, resulta mucho más fácil acercarse a otros algoritmos como Bellman-Ford, Floyd-Warshall o A*.

Recursos adicionales

• Artículo de Wikipedia sobre el algoritmo de Dijkstra
• Visualización interactiva del algoritmo de Dijkstra en VisuAlgo
• Explicación de Dijkstra en GeeksforGeeks
• Curso de Coursera sobre grafos y estructuras de datos