Dijkstra vs Bellman-Ford vs Floyd-Warshall

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La respuesta corta

El algoritmo de Dijkstra, el algoritmo de Bellman-Ford y el algoritmo de Floyd-Warshall encuentran caminos más cortos en un grafo ponderado, pero responden a preguntas distintas en condiciones distintas. Dos preguntas deciden entre ellos: ¿necesitas distancias desde un único origen o entre todos los pares de vértices? y ¿puede una arista tener un peso negativo?

Aquí V es el número de vértices y E el número de aristas. En una frase: usa Dijkstra por defecto, cambia a Bellman-Ford cuando los pesos puedan ser negativos, y usa Floyd-Warshall cuando necesites la tabla de distancias completa de un grafo con a lo sumo unos pocos cientos de vértices. Cuando necesites todos los pares en un grafo grande y disperso con aristas negativas, el algoritmo de Johnson de la sección 7 combina los dos primeros. El resto de esta guía ejecuta los tres sobre el mismo grafo y muestra dónde gana y dónde falla cada uno.

2. Un grafo, tres respuestas

El ejemplo que nos acompaña es un pequeño grafo dirigido con seis vértices, siete aristas y una arista negativa, B → A con peso -4. Piensa en los pesos como costes: un coste negativo es un reembolso, como una carretera de peaje que te paga por usarla, o un paso de un proceso químico que libera energía.

S → A  3      S → B  6      A → C  4      B → A  -4
C → T  2      B → D  3      D → T  4

6 vértices, 7 aristas, sin ciclos; origen S

La ruta más barata de S a T es S, B, A, C, T, con coste 6 - 4 + 4 + 2 = 8. Empieza por el primer paso más caro, hacia B, y lo recupera con el reembolso. El programa siguiente implementa los tres algoritmos en su forma estándar de libro de texto y los ejecuta desde S.

import heapq
INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def dijkstra(adj, s):
    """Voraz: cierra el vértice abierto más cercano y no vuelve a visitarlo."""
    dist = {v: INF for v in adj}
    dist[s] = 0
    done, heap = set(), [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue                      # entrada obsoleta del montículo
        done.add(u)
        for v, w in adj[u]:
            if v not in done and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def bellman_ford(adj, s):
    """Relaja todas las aristas, ronda tras ronda, hasta que nada cambie."""
    dist = {v: INF for v in adj}
    dist[s] = 0
    for _ in range(len(adj) - 1):
        changed = False
        for u in adj:
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    changed = True
        if not changed:
            break
    return dist

def floyd_warshall(adj):
    """Todos los pares: admite los vértices como escalas de uno en uno."""
    d = {u: {v: 0 if u == v else INF for v in adj} for u in adj}
    for u in adj:
        for v, w in adj[u]:
            d[u][v] = min(d[u][v], w)
    for k in adj:
        for i in adj:
            for j in adj:
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

G = graph([('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
           ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)])
dj, bf, fw = dijkstra(G, 'S'), bellman_ford(G, 'S'), floyd_warshall(G)['S']
for v in G:
    print(v, dj[v], bf[v], fw[v], '' if dj[v] == bf[v] else '<- Dijkstra is wrong')
# S 0 0 0
# A 3 2 2 <- Dijkstra is wrong
# B 6 6 6
# C 7 6 6 <- Dijkstra is wrong
# T 9 8 8 <- Dijkstra is wrong
# D 9 9 9

Bellman-Ford y Floyd-Warshall devuelven las distancias verdaderas. Dijkstra da 3 para A, 7 para C y 9 para T, todas demasiado altas, y no lanza ningún error: las respuestas erróneas parecen exactamente correctas. La sección 4 explica por qué. En un grafo con pesos no negativos los tres coincidirían, y la única diferencia sería la velocidad.

3. Qué hace cada algoritmo

Los tres algoritmos se construyen a partir de una sola operación, la relajación. Cada vértice v lleva una distancia provisional dist[v], que empieza en infinito, o en 0 para el origen. Relajar la arista u → v con peso w consiste en preguntar si pasar por u es más barato y, si lo es, anotarlo:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Una distancia provisional solo puede bajar, y siempre es el coste de alguna ruta real. Los algoritmos solo se diferencian en qué aristas relajan y en qué orden.

• Dijkstra mantiene los vértices abiertos en una cola de prioridad. Toma repetidamente el que tiene la menor distancia provisional, declara esa distancia definitiva y relaja sus aristas salientes. Cada vértice se cierra una vez y cada arista se relaja una vez. Edsger Dijkstra lo diseñó en 1956, en unos veinte minutos según su propio relato, y lo publicó en 1959. La guía del algoritmo de Dijkstra lo recorre paso a paso.
• Bellman-Ford no toma decisiones. Relaja todas las aristas, en cualquier orden fijo, y repite. Un camino más corto sin ciclos tiene a lo sumo V - 1 aristas, y tras la ronda i ya se han encontrado todos los caminos más cortos con a lo sumo i aristas, así que V - 1 rondas siempre bastan. El nombre une a Richard Bellman, que publicó el método por rondas en 1958, y a Lester Ford, cuyo artículo de 1956 dio la regla general de relajar aristas hasta que nada mejore. Alfonso Shimbel y Edward Moore encontraron métodos equivalentes en esos mismos años. La guía del algoritmo de Bellman-Ford demuestra la cota.
• Floyd-Warshall calcula toda la tabla de una vez. Admite los vértices como escalas de uno en uno: tras el paso k, la entrada [i][j] guarda la ruta más barata de i a j cuyos vértices intermedios proceden todos de los k primeros. Tres bucles anidados y una línea de aritmética. Bernard Roy en 1959 y Stephen Warshall en 1962 publicaron el mismo esquema para la alcanzabilidad, y Robert Floyd lo adaptó a los caminos más cortos en 1962. La guía del algoritmo de Floyd-Warshall deduce la recurrencia.

En el ejemplo, Bellman-Ford recorre las aristas en el orden en que se listaron. Su primera ronda ya baja A a 2 cuando llega a las aristas que salen de B, pero para entonces ya ha usado el valor antiguo 3 para fijar C = 7. La segunda ronda traslada la mejora a C = 6 y T = 8. La tercera ronda no cambia nada, así que el algoritmo se detiene antes de tiempo en lugar de ejecutar las V - 1 = 5 rondas. Cuántas rondas hacen falta depende del orden de las aristas, pero nunca son más de V - 1.

4. Por qué Dijkstra falla con aristas negativas

La velocidad de Dijkstra procede de una promesa: cuando un vértice sale de la cola de prioridad, su distancia es definitiva. La promesa se apoya en un argumento que necesita pesos no negativos. Supón que u es el vértice abierto más cercano. Cualquier otra ruta hacia u tiene que salir de la región cerrada a través de algún vértice abierto x, que ya está al menos tan lejos como u, y el resto de la ruta solo puede sumar coste. Con una arista negativa, el resto de la ruta puede restar coste, y el argumento se viene abajo.

Eso es exactamente lo que ocurre en el ejemplo. Dijkstra cierra S en 0 y después A en 3, porque 3 es menor que el valor de B, que es 6. Cuando B se cierra y su arista hacia A ofrece 6 - 4 = 2, A ya es definitivo y la mejora se descarta. Todo lo construido sobre A hereda el error: C se cierra en 3 + 4 = 7 en lugar de 6, y T en 9 en lugar de 8.

Dos arreglos tentadores no funcionan:

• Sumar una constante a cada peso. Sumar 4 hace que todos los pesos sean no negativos, pero cobra 4 por cada arista, así que las rutas con más aristas salen más penalizadas. En el grafo desplazado, Dijkstra encuentra S, A, C, T, con coste desplazado 21 frente a 24 para la verdadera ruta más corta S, B, A, C, T, que tiene una arista más. Con los pesos originales esa ruta cuesta 9, no 8. El algoritmo de Johnson de la sección 7 muestra el repesado que sí funciona.
• Permitir que los vértices cerrados se reabran. Si un vértice puede volver a entrar en la cola cada vez que baja su distancia, el algoritmo pasa a ser correcto con aristas negativas siempre que no haya ningún ciclo negativo. Pero la promesa que lo hacía rápido desaparece, y Donald Johnson demostró en 1973 que el algoritmo de Dijkstra adaptado de esta forma para admitir aristas negativas puede tardar un tiempo exponencial, del orden de n 2n pasos en una familia de grafos con n vértices. Llegados a ese punto, el O(V E) garantizado de Bellman-Ford es la opción más segura.

Con pesos no negativos no surge nada de esto, y Dijkstra es correcto y el más rápido de los tres. Los pesos cero no son ningún problema: el argumento solo necesita que ninguna arista reduzca el coste.

5. Ciclos negativos

Un ciclo negativo es un ciclo cuyos pesos suman menos de cero. Si se puede alcanzar desde el origen y puede alcanzar el destino, no existe ninguna ruta más corta: dar una vuelta más al ciclo siempre sale más barato. La distancia es menos infinito, y un algoritmo debería informar del ciclo en lugar de dar un número. Añade la arista C → B con peso -5 al ejemplo y el ciclo B, A, C, B cuesta -4 + 4 - 5 = -5.

• Bellman-Ford lo detecta con una ronda extra. Sin un ciclo negativo, nada puede mejorar tras V - 1 rondas; si la ronda V todavía baja alguna distancia, existe un ciclo negativo, y seguir los punteros a los padres hacia atrás desde el vértice que ha cambiado lleva hasta él.
• Floyd-Warshall lo detecta en la diagonal. La entrada [v][v] empieza en 0 y solo puede volverse negativa si hay una ruta cerrada que pasa por v con peso total negativo. Así que existe un ciclo negativo exactamente cuando alguna entrada de la diagonal termina por debajo de cero. Una vez que eso ocurre, las demás entradas ya no son distancias con sentido, y Stefan Hougardy demostró en 2010 que pueden crecer hasta valores exponencialmente grandes, así que lo más seguro es comprobar la diagonal dentro del bucle y detenerse en cuanto una entrada se vuelva negativa.
• Dijkstra no puede detectarlo. Simplemente da por hecho que esa situación no se presenta.

INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def negative_cycle(adj):
    """Bellman-Ford desde un origen virtual unido a cada vértice con coste 0.
    Devuelve un ciclo negativo como lista de vértices, o None."""
    dist = {v: 0 for v in adj}
    parent = {v: None for v in adj}
    for _ in range(len(adj)):                  # una ronda más de lo habitual
        last = None
        for u in adj:
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v], parent[v], last = dist[u] + w, u, v
        if last is None:
            return None                        # una ronda sin cambios: no hay ciclo negativo
    for _ in range(len(adj)):                  # retrocede lo suficiente para caer en el ciclo
        last = parent[last]
    cycle, v = [last], parent[last]
    while v != last:                           # sigue los padres una vuelta al ciclo
        cycle.append(v)
        v = parent[v]
    cycle.reverse()                            # los padres apuntan hacia atrás
    return cycle + cycle[:1]

def floyd_warshall_diagonal(adj):
    """Vértices cuya distancia a sí mismos resulta negativa."""
    d = {u: {v: 0 if u == v else INF for v in adj} for u in adj}
    for u in adj:
        for v, w in adj[u]:
            d[u][v] = min(d[u][v], w)
    for k in adj:
        for i in adj:
            for j in adj:
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return [v for v in adj if d[v][v] < 0]

edges = [('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
         ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)]
print(negative_cycle(graph(edges)))
# None
bad = graph(edges + [('C', 'B', -5)])          # B -> A -> C -> B cuesta -4 + 4 - 5 = -5
print(negative_cycle(bad))
# ['C', 'B', 'A', 'C']
print(floyd_warshall_diagonal(bad))
# ['A', 'B', 'C']

La función inicia Bellman-Ford desde un origen virtual unido a cada vértice con coste 0, así que encuentra un ciclo negativo en cualquier parte del grafo, no solo uno alcanzable desde S. En el ejemplo original, una ronda acaba por no cambiar nada y la función devuelve None. Con la arista extra devuelve el ciclo C, B, A, C, el mismo ciclo escrito desde otro inicio, y Floyd-Warshall marca A, B y C en su diagonal. En pruebas con miles de grafos aleatorios, la diagonal señaló un ciclo negativo exactamente cuando existía uno, pero no siempre marcó todos los vértices que pueden alcanzarlo, así que úsala como una prueba de sí o no.

Hay una trampa en la que cae mucha gente. En un grafo no dirigido cada arista puede recorrerse en ambos sentidos, así que una sola arista con peso negativo ya es un ciclo negativo: u, v, u. Por tanto, Bellman-Ford ejecutado sobre la versión dirigida de un grafo no dirigido informará de un ciclo negativo siempre que alguna arista sea negativa, un escollo que detalla el libro Algorithms de Sedgewick y Wayne. Los caminos simples más cortos con pesos negativos en grafos no dirigidos requieren métodos distintos y más complejos.

6. Velocidad: cuál es más rápido y cuándo

Para un solo origen, el orden está claro siempre que Dijkstra sea aplicable: O((V + E) log V) con un montículo binario frente al O(V E) de Bellman-Ford. En un grafo con 10.000 vértices y 50.000 aristas, eso supone aproximadamente un millón de pasos de montículo frente a hasta 500 millones de relajaciones de aristas. Floyd-Warshall no es un método desde un único origen, y ejecutarlo para un solo origen desperdicia casi todo su trabajo.

Para todos los pares la comparación está más reñida, porque las alternativas consisten en ejecutar un algoritmo desde un único origen a partir de cada vértice:

Las cotas asintóticas ocultan constantes, así que el programa siguiente cuenta los pasos básicos que cada método realiza de verdad en dos grafos dirigidos aleatorios con 100 vértices: uno disperso con 300 aristas y uno denso con 4950, la mitad de todas las aristas posibles. Para Dijkstra cuenta por separado las comprobaciones de aristas y las operaciones del montículo, ya que una operación del montículo cuesta unos log V pasos.

import heapq, random
INF = float('inf')

def random_graph(n, m, seed):
    """n vértices, m aristas dirigidas distintas con pesos 1..100."""
    rnd = random.Random(seed)
    pairs = rnd.sample([(u, v) for u in range(n) for v in range(n) if u != v], m)
    adj = {v: [] for v in range(n)}
    for u, v in pairs:
        adj[u].append((v, rnd.randint(1, 100)))
    return adj

def all_pairs_dijkstra(adj):
    """Dijkstra desde cada vértice. Cuenta comprobaciones de aristas y operaciones del montículo."""
    checks = heap_ops = 0
    for s in adj:
        dist, heap = {v: INF for v in adj}, [(0, s)]
        dist[s] = 0
        while heap:
            d, u = heapq.heappop(heap)
            heap_ops += 1
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                checks += 1
                if d + w < dist[v]:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))
                    heap_ops += 1
    return checks, heap_ops

def all_pairs_bellman_ford(adj):
    """Bellman-Ford desde cada vértice, con parada anticipada cuando una ronda no cambia nada."""
    m, checks = sum(len(a) for a in adj.values()), 0
    for s in adj:
        dist = {v: INF for v in adj}
        dist[s] = 0
        for _ in range(len(adj) - 1):
            changed = False
            for u in adj:
                for v, w in adj[u]:
                    if dist[u] + w < dist[v]:
                        dist[v], changed = dist[u] + w, True
            checks += m
            if not changed:
                break
    return checks

n = 100
for name, m in [('sparse', 3 * n), ('dense', n * (n - 1) // 2)]:
    adj = random_graph(n, m, seed=1)
    checks, heap_ops = all_pairs_dijkstra(adj)
    print(f'{name:6} E={m:4}  Dijkstra x V: {checks:7,} checks + {heap_ops:6,} heap ops   '
          f'Bellman-Ford x V: {all_pairs_bellman_ford(adj):9,}   Floyd-Warshall: {n ** 3:,}')
# sparse E= 300  Dijkstra x V:  27,565 checks + 21,388 heap ops   Bellman-Ford x V:   226,200   Floyd-Warshall: 1,000,000
# dense  E=4950  Dijkstra x V: 495,000 checks + 64,770 heap ops   Bellman-Ford x V: 2,712,600   Floyd-Warshall: 1,000,000

En el grafo disperso, Dijkstra desde cada vértice necesita unos 49.000 pasos frente al 1.000.000 fijo de Floyd-Warshall, un factor de unos 20. En el grafo denso la diferencia casi desaparece y, una vez que se cuenta el coste logarítmico de cada operación del montículo, el sencillo bucle interno de Floyd-Warshall, que recorre la memoria en orden y no necesita cola de prioridad, suele ganar en la práctica. Bellman-Ford desde cada vértice es el más lento en ambos casos, incluso con parada anticipada. La regla práctica: por debajo de unos pocos cientos de vértices, o cuando la mayoría de los pares de vértices están unidos por una arista, usa Floyd-Warshall por su sencillez; en grafos grandes y dispersos, usa Dijkstra o Johnson desde cada vértice.

7. Todos los pares con aristas negativas: el algoritmo de Johnson

El algoritmo de Donald Johnson, de 1977, aprovecha lo mejor de ambos. Ejecuta Bellman-Ford una vez para calcular un número h(v) para cada vértice, la distancia desde un origen virtual unido a todos los vértices con coste 0. Después sustituye cada peso por

w'(u, v) = w(u, v) + h(u) - h(v)

Como h cumple h(v) ≤ h(u) + w(u, v) para toda arista, todos los pesos nuevos son no negativos. Y a lo largo de cualquier ruta de s a t los términos se cancelan de forma telescópica, así que el coste de toda ruta cambia en la misma cantidad, h(s) - h(t). Las rutas más cortas siguen siendo las más cortas, y ahora se puede ejecutar Dijkstra desde cada vértice. A diferencia de sumar una constante, este repesado no depende de cuántas aristas tenga una ruta.

import heapq
INF = float('inf')

def graph(edges):
    adj = {}
    for u, v, w in edges:
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, [])
    return adj

def dijkstra(adj, s):
    dist, heap = {v: INF for v in adj}, [(0, s)]
    dist[s] = 0
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

def johnson(adj):
    """Todos los pares con aristas negativas: un Bellman-Ford y luego Dijkstra desde cada vértice."""
    h = {v: 0 for v in adj}                    # distancias desde un origen virtual
    for _ in range(len(adj)):
        for u in adj:
            for v, w in adj[u]:
                h[v] = min(h[v], h[u] + w)
    for u in adj:
        for v, w in adj[u]:
            if h[u] + w < h[v]:
                raise ValueError('negative cycle')
    # repesado: toda arista pasa a ser no negativa, todo camino cambia en h[s] - h[t]
    lifted = {u: [(v, w + h[u] - h[v]) for v, w in adj[u]] for u in adj}
    return {s: {t: d - h[s] + h[t] for t, d in dijkstra(lifted, s).items()} for s in adj}, lifted

G = graph([('S', 'A', 3), ('S', 'B', 6), ('A', 'C', 4), ('B', 'A', -4),
           ('C', 'T', 2), ('B', 'D', 3), ('D', 'T', 4)])
dist, lifted = johnson(G)
print({u: [(v, w) for v, w in lifted[u]] for u in ('S', 'A', 'B')})
# {'S': [('A', 7), ('B', 6)], 'A': [('C', 0)], 'B': [('A', 0), ('D', 3)]}
print(dist['S'])
# {'S': 0, 'A': 2, 'B': 6, 'C': 6, 'T': 8, 'D': 9}
print(dist['B'])
# {'S': inf, 'A': -4, 'B': 0, 'C': 0, 'T': 2, 'D': 3}

En el ejemplo, h(A) = -4 y todos los demás vértices reciben 0. La arista negativa B → A pasa a valer 0, S → A sube de 3 a 7 y A → C baja de 4 a 0, y Dijkstra con los nuevos pesos, corregido de vuelta con h, da las distancias verdaderas desde cada origen, incluida la fila de B con su entrada negativa -4. Si Bellman-Ford encuentra un ciclo negativo en el primer paso, el algoritmo de Johnson se detiene e informa de él.

8. Cuando ninguno de los tres es la mejor opción

Algunos grafos tienen una estructura que un método más sencillo o más rápido puede aprovechar:

• Grafos no ponderados. Si cada arista cuenta como 1, la búsqueda en anchura encuentra todas las distancias desde un origen en O(V + E). Dijkstra daría la misma respuesta más despacio. Consulta BFS vs DFS.
• Grafos acíclicos. En un grafo acíclico dirigido, procesa los vértices en orden topológico y relaja una vez las aristas salientes de cada vértice. Eso cuesta O(V + E) y funciona con pesos negativos. El grafo de ejemplo no tiene ciclos, así que este método lo habría resuelto en una sola pasada.
• Solo pesos 0 y 1. Una cola doble sustituye a la cola de prioridad: las aristas de peso 0 van al frente y las de peso 1 al final, lo que da tiempo lineal.
• Un origen y un destino con una buena estimación. La búsqueda A* añade una estimación de la distancia restante a la prioridad de Dijkstra y explora muchos menos vértices en mapas. Consulta el algoritmo de búsqueda A*.

9. Memoria y recuperación de los caminos

A menudo las distancias no bastan: quieres la ruta en sí. Dijkstra y Bellman-Ford guardan un padre por vértice, el vértice desde el que llegó la mejor ruta, y la ruta hasta t se lee hacia atrás desde t. Eso cuesta O(V) de memoria adicional. Floyd-Warshall necesita una tabla completa de V por V con entradas de "siguiente salto" junto a su tabla de distancias, así que su memoria es O(V2). Con 10.000 vértices y entradas de 8 bytes, solo la tabla de distancias ocupa unos 800 megabytes, y la tabla de siguientes saltos añade otro tanto. Más que el tiempo, lo que suele descartar Floyd-Warshall en grafos grandes es la memoria.

10. Dónde se usa cada uno

• Dijkstra es la opción por defecto allí donde los costes son físicos: la navegación por carretera, las conexiones de vuelos y los protocolos de enrutamiento de estado de enlace de internet, como OSPF, en los que cada router calcula caminos más cortos sobre un mapa de la red.
• Bellman-Ford encaja en entornos donde cada nodo solo conoce a sus vecinos. Los protocolos de enrutamiento por vector de distancias, como RIP, repiten su paso de relajación por toda la red, y cada router actualiza su tabla a partir de las tablas de sus vecinos. Su capacidad para encontrar ciclos negativos se usa para detectar arbitraje de divisas: con pesos -log(tasa), una secuencia de operaciones que termina con más dinero del que había al principio es exactamente un ciclo negativo.
• Floyd-Warshall rellena tablas de distancias completas para grafos pequeños: matrices de distancias para el agrupamiento o el problema del viajante de comercio, y la clausura transitiva, la cuestión de qué vértices pueden alcanzar a cuáles, que es la versión que publicó Warshall.

11. Un área de investigación todavía activa

Los caminos más cortos son uno de los problemas más antiguos de la algoritmia, y las cotas siguen moviéndose. En 2022, Aaron Bernstein, Danupon Nanongkai y Christian Wulff-Nilsen demostraron que los caminos más cortos desde un único origen con pesos enteros negativos se pueden resolver en tiempo casi lineal, muy por debajo del O(V E) de Bellman-Ford. En 2024, Bernhard Haeupler y sus coautores demostraron que el algoritmo de Dijkstra con un montículo diseñado adecuadamente es universalmente óptimo para ordenar los vértices por distancia: en cada grafo fijo, su peor caso sobre todos los pesos de las aristas está a un factor constante de lo mejor que puede hacer cualquier algoritmo. Y en 2025, Ran Duan y sus coautores presentaron un algoritmo determinista para grafos dirigidos con pesos no negativos que se ejecuta en tiempo O(E log2/3 V) y supera el O(E + V log V) de Dijkstra en grafos dispersos. Escapa de lo que durante mucho tiempo se llamó la barrera de la ordenación porque, a diferencia de Dijkstra, no produce los vértices en orden de distancia. Cada uno de los tres artículos ganó un premio al mejor artículo. Ninguno de ellos ha sustituido todavía a los tres clásicos en el código de cada día, donde importan más la sencillez y las constantes pequeñas.

12. Errores comunes

13. Glosario

15. Referencias

Los algoritmos, las cotas y las atribuciones anteriores proceden de estas fuentes, listadas en orden cronológico.

1. Shimbel, A. (1955). "Structure in Communication Nets." En Proceedings of the Symposium on Information Networks, 199 a 203. Brooklyn: Polytechnic Press of the Polytechnic Institute of Brooklyn.
2. Ford, L. R. (1956). Network Flow Theory. Documento P-923. Santa Monica: RAND Corporation.
3. Bellman, R. (1958). "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 87 a 90.
4. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs." Numerische Mathematik 1, 269 a 271.
5. Moore, E. F. (1959). "The Shortest Path Through a Maze." En Proceedings of an International Symposium on the Theory of Switching, 285 a 292. Cambridge, MA: Harvard University Press.
6. Roy, B. (1959). "Transitivité et connexité." Comptes Rendus de l'Académie des Sciences 249, 216 a 218.
7. Floyd, R. W. (1962). "Algorithm 97: Shortest Path." Communications of the ACM 5(6), 345.
8. Warshall, S. (1962). "A Theorem on Boolean Matrices." Journal of the ACM 9(1), 11 a 12.
9. Johnson, D. B. (1973). "A Note on Dijkstra's Shortest Path Algorithm." Journal of the ACM 20(3), 385 a 388.
10. Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks." Journal of the ACM 24(1), 1 a 13.
11. Fredman, M. L. y Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM 34(3), 596 a 615.
12. Moy, J. (1998). "OSPF Version 2." RFC 2328. Internet Engineering Task Force.
13. Malkin, G. (1998). "RIP Version 2." RFC 2453. Internet Engineering Task Force.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición. Cambridge, MA: MIT Press.
15. Frana, P. L. y Misa, T. J. (2010). "An Interview with Edsger W. Dijkstra." Communications of the ACM 53(8), 41 a 47.
16. Hougardy, S. (2010). "The Floyd-Warshall Algorithm on Graphs with Negative Cycles." Information Processing Letters 110(8 a 9), 279 a 281.
17. Sedgewick, R. y Wayne, K. (2011). Algorithms, 4.ª edición. Upper Saddle River, NJ: Addison-Wesley.
18. Schrijver, A. (2012). "On the History of the Shortest Path Problem." Documenta Mathematica, Extra Volume ISMP, 155 a 167.
19. Bernstein, A., Nanongkai, D. y Wulff-Nilsen, C. (2022). "Negative-Weight Single-Source Shortest Paths in Near-linear Time." Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science, 600 a 611.
20. Haeupler, B., Hladík, R., Rozhoň, V., Tarjan, R. E. y Tětek, J. (2024). "Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps." Proceedings of the 65th IEEE Symposium on Foundations of Computer Science, 2099 a 2130.
21. Duan, R., Mao, J., Mao, X., Shu, X. y Yin, L. (2025). "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths." Proceedings of the 57th ACM Symposium on Theory of Computing, 36 a 44.