Teoría de Grafos: Algoritmo de Dijkstra es superado tras 65 años

Ruta más corta en grafos: algoritmo supera a Dijkstra tras 65 años (con una pizca de sal)

Cada vez que tomas un Uber, pides un Rappi o usas Google Maps, existe un problema computacional que toda aplicación debe resolver. Y puede que desde hoy, resolverlo sea más rápido:

Dado un punto A y un punto B ¿cuál es el camino más corto para llegar desde A hasta B?.

Este problema, conocido como el problema de la ruta más corta u óptima, ha perseguido a la humanidad desde hace siglos. Por ejemplo, en el siglo III a.C. Euclides demostró que una línea recta era siempre más corta que cualquier camino quebrado. O en el siglo XI, astrónomos islámicos resolvían cálculos de geometría esférica para encontrar la qibla, la dirección más corta hacia La Meca desde cualquier punto del planeta.

Hasta que en 1958 los matemáticos Richard Bellman y Lester Ford Jr. formalizaron el asunto como un problema de búsqueda en grafos, y propusieron un algoritmo para resolverlo.

Hace unas semanas, un grupo de investigadores presentaron un nuevo algoritmo capaz de resolver el problema con mayor eficiencia que cualquier otra solución de los últimos 65 años.

Pero antes de avanzar, sé lo que te estás preguntando.

¿Qué es un grafo?

En términos simples, un grafo consiste en un mapa de puntos (denominados vértices) conectados con líneas (denominadas aristas) que pueden tener asignado algún valor (denominado peso). Normalmente, los grafos se utilizan para representar relaciones entre entidades. Algunos ejemplos:

• En un grafo de una red social, los vértices podrían ser las personas y las aristas representan si pares de personas son conocidas entre sí.
• En un grafo de una aerolínea, los vértices podrían ser ciudades y las aristas representan a los vuelos directos entre pares de ciudades. El peso de cada arista puede ser la distancia entre las ciudades adyacentes.

Los grafos son una formalización del concepto matemático de relación, y su uso práctico en general recae en diversas áreas de investigación operativa y computación. Existen varios problemas clásicos dentro del área de Teoría de Grafos, acá algunos de los más emblemáticos aplicados en ingeniería:

• Ruta mínima: encontrar el camino más corto entre dos puntos.
• El vendedor viajero: visitar todas las ciudades de un mapa una vez y volver al inicio gastando lo menos posible.
• Coloración de mapas: colorear regiones (o nodos) sin que dos vecinas tengan el mismo color.
• Ciclo euleriano: recorrer todas las calles de un mapa y volver al inicio, pasando cada calle exactamente una vez.

En particular, para el problema de ruta mínima, la mejor solución que se había encontrado fue el algoritmo publicado por Edsger Dijkstra en 1959. Un dato anecdótico: según Dijkstra, la solución la diseñó en 20 minutos luego de una conversación que tuvo con su prometida sobre su futura boda. En su desayuno, discutían cómo los invitados llegarían desde otras ciudades de Países Bajos hacia Groningen de la manera más eficiente posible:

“¿Cuál es la forma más corta de viajar de Róterdam a Groningen? Ese problema me llevó a diseñar, en unos veinte minutos, el algoritmo de ruta más corta. Surgió una mañana en Ámsterdam, sentado en una terraza con mi prometida. Lo hice sin lápiz ni papel, lo que me obligó a evitar complejidades innecesarias. Publicado en 1959, terminó siendo, para mi sorpresa, una de las bases de mi fama.” –Edsger Dijkstra, Turing Award de 1972.

Este algoritmo resultó ser más rápido que el inicial planteado por Bellman y Ford, y se mantuvo, por 65 años, como la solución más eficiente para encontrar la ruta mínima entre dos vértices en un grafo. Hasta hoy, la rutina de Dijkstra sigue siendo materia obligatoria en ingeniería industrial, computación y matemáticas aplicadas.

¿Cómo funciona el algoritmo de Dijkstra?

La rutina de Dijkstra consiste en explorar desde el primer vértice (origen) hacia los inmediatamente más cercanos de manera iterativa hasta encontrar la ruta más corta desde el inicio hasta cada vértice del grafo. Podemos dividir este algoritmo en 4:

Inicialización: se asigna distancia 0 al vértice de origen y ∞ (infinito) al resto. Estas distancias las iremos actualizando en cada paso, y las guardamos en una estructura —normalmente una cola de prioridad— para seleccionar siempre el vértice con menor distancia provisional.

Exploración: se extrae de la cola el vértice v más cercano no visitado y se evalúan sus aristas: para cada vecino v’ de v, si la distancia actual de v’ al origen es mayor que la distancia desde el origen hasta v actual más el peso de la arista vv’, se actualiza con este nuevo valor.

Repetición: el proceso continúa seleccionando el siguiente vértice con menor distancia pendiente y evaluando sus aristas.

Finalización: el algoritmo termina cuando todos los vértices han sido visitados.

El principio clave es que, una vez que un vértice es extraído como el de menor distancia provisional, esa distancia ya es la mínima posible. Por eso, Dijkstra garantiza una solución óptima en grafos con pesos positivos y es muy eficiente en la práctica, sobre todo si se implementa con estructuras como un heap binario o cola de prioridad.

Acá un pseudocódigo del algoritmo:

1  función Dijkstra(Grafo, origen):
2      
3      para cada vértice v en Grafo.Vértices:
4          dist[v] ← INFINITO
5          prev[v] ← INDEFINIDO
6          agregar v a Q
7      dist[origen] ← 0
8      
9      mientras Q no esté vacía:
10          u ← vértice en Q con menor dist[u]
11          eliminar u de Q
12          
13          para cada vecino v de u que aún esté en Q:
14              alt ← dist[u] + Grafo.Arista(u, v)
15              si alt < dist[v]:
16                  dist[v] ← alt
17                  prev[v] ← u
18
19      devolver dist[], prev[]

Como mencionamos antes, este algoritmo es muy eficiente en términos de complejidad computacional (recursos que le toma a un computador ejecutarlo). En el caso general, si n es la cantidad de vértices y m la cantidad de aristas, el algoritmo de Dijkstra tiene una complejidad de O(m + n log n). En otras palabras, el número de operaciones que debe realizar un computador crece, aproximadamente, a una tasa de m + n log n a medida que aumenta el tamaño del grafo. Este tipo de complejidades se conocen como poli­nomiales, y suelen ser rápidas de ejecutar en un computador tradicional.

Algoritmo de Reducción de Frontera (Duan et al, 2025)

Como dijimos antes, tuvieron que pasar 65 años para destronar a Dijkstra. En julio de 2025, un equipo de investigadores liderado por Ran Duan de la Universidad de Tsinghua presentó un nuevo algoritmo capaz de resolver el problema de ruta mínima en tiempo O(m log²/³ n), superando por primera vez la barrera de O(m + n log n) del algoritmo de Dijkstra.

La innovación: reducción de frontera

El truco está en combinar lo mejor de dos mundos: Dijkstra (que ordena vértices pero es costoso) y Bellman-Ford (que no ordena pero es lento). La clave de todo esto es el concepto de «frontera»: imagina que en Dijkstra dividimos los vértices del grafo en tres grupos según su estado de exploración:

Completos: vértices con distancia definitiva calculada y cuyos vecinos ya han sido procesados.

Frontera (S): vértices alcanzados (con distancia estimada < ∞) pero cuyos vecinos aún no han sido procesados.

No alcanzados: vértices con distancia infinita.

Por un lado, en el algoritmo de Dijkstra tradicional, la frontera tiene todos los «candidatos» que podrías visitar próximamente. El problema surge porque la frontera (y el costo de computarla) en algunos casos crece linealmente con el tamaño del grafo, o en otras palabras cuando esta frontera crece hasta contener O(n) vértices, te obliga a mantener un orden total entre ellos (lo que es costoso) —y aquí es donde aparece la barrera de ordenamiento Ω(n log n) (la cota de complejidad inferior de Dijkstra).

Por otro lado, el nuevo algoritmo (en lugar de mantener todos los vértices en la frontera) utiliza una rutina del tipo “divide y vencerás” para determinar un conjunto más pequeño de vértices «pivote» que son suficientes para encontrar las rutas más cortas. Específicamente:

• Si la frontera tiene muchos vértices (más de k veces el tamaño deseado), el algoritmo la reduce a 1/k de su tamaño original.
• Si la frontera es pequeña, ejecuta k pasos del algoritmo de Bellman-Ford para completar los vértices cercanos y luego identifica los pivotes —vértices que tienen rutas más cortas con al menos k descendientes.

Donde k = log^(1/3)(n), lo que resulta en la mejora de complejidad observada.

función BMSSP(l, B, S)
    si l = 0 entonces
        retornar CasoBase(B, S)
    
    P, W ← EncontrarPivotes(B, S)
    D.Inicializar(M = 2^((l - 1) * t), B)       // Estructura de datos especial
    D.Insertar(⟨x, d̂[x]⟩) para cada x ∈ P
    
    i ← 0
    B'₀ ← min(d̂[x] para cada x ∈ P)
    U ← ∅
    
    mientras |U| < k * 2^(l * t) y D no esté vacío hacer
        i ← i + 1
        Bᵢ, Sᵢ ← D.Extraer()                    // Obtiene los M elementos más pequeños
        B'ᵢ, Uᵢ ← BMSSP(l - 1, Bᵢ, Sᵢ)          // Llamada recursiva
        U ← U ∪ Uᵢ
        K ← ∅
        
        para cada arista (u, v) donde u ∈ Uᵢ hacer
            si d̂[u] + wᵤᵥ ≤ d̂[v] entonces
                d̂[v] ← d̂[u] + wᵤᵥ
                si d̂[u] + wᵤᵥ ∈ [Bᵢ, B) entonces
                    D.Insertar(⟨v, d̂[u] + wᵤᵥ⟩)
                sino si d̂[u] + wᵤᵥ ∈ [B'ᵢ, Bᵢ) entonces
                    K ← K ∪ {⟨v, d̂[u] + wᵤᵥ⟩}
        
        D.PreAnexarEnLote(
            K ∪ {⟨x, d̂[x]⟩ : x ∈ Sᵢ y d̂[x] ∈ [B'ᵢ, Bᵢ)}
        )
        
    retornar B' ← min{B'ᵢ, B}; 
             U ← U ∪ {x ∈ W : d̂[x] < B'}

Una pizca de sal

Algo importante de mencionar, es que esta mejora algorítmica, sólo es significativa en grafos dispersos (donde m ≤ n), o sea, grafos que no tienen tantas aristas. En el caso contrario, es decir, en grafos densos (m ≈ n²), la diferencia es menos pronunciada. De esta manera, si antes decíamos que Djisktra era el mejor algoritmo para el caso general (cualquier grafo), este nuevo algoritmo re-posiciona la discusión: para grafos dispersos el algoritmo de reducción supera a Dijkstra, mientras que en el caso denso Dijkstra sigue siendo el rey.

Otro aspecto relevante, es que todo el análisis de complejidad busca entender cómo se comportan la cantidad de operaciones realizadas por el algoritmo en términos asintóticos. Esto es, cómo crece la cantidad de comparaciones a medida que el tamaño del input crece (i.e. el tamaño grafo crece). Sin embargo, este tipo de análisis suele ocultar costos “constantes” de ejecutar el algoritmo, lo que hace que en la práctica pueda ser más lento.

Finalmente, otro punto a favor de Dijkstra en comparación con el nuevo algoritmo es la sencillez de la rutina, lo que facilita su implementación y explicación, al menos a nivel didáctico.

¿Qué implicancias prácticas tiene todo esto?

Como mencionamos al inicio, el problema de la ruta más corta está presente en nuestra vida cotidiana. Mejoras algorítmicas que permitan encontrar rutas óptimas más rápido pueden tener efectos concretos: desde reducir el tráfico vehicular, agilizar la entrega de comida o productos, hasta mejorar la experiencia en videojuegos disminuyendo el lag.

En cualquier caso, este avance es altamente relevante para las Ciencias de la Computación. Es probable que, a partir de ahora, los libros de texto universitarios incluyan, al menos, una nota al pie mencionando el nuevo Algoritmo de Reducción de Frontera.

Fuente: https://fintualist.com/chile/

Equipo Prensa
Portal Educa