Algoritmo de Dijkstra y caminos mínimos: Bellman-Ford, Floyd-Warshall y A*

Abrir el simulador

Mira Dijkstra paso a paso sobre un grafo: frontera, distancias y camino más corto.

¿Cuál es la ruta más rápida de Madrid a Barcelona? ¿Por qué camino debe enviar un router cada paquete? Son problemas de caminos mínimos en un grafo con pesos. El algoritmo de Dijkstra (1956) los resuelve de forma eficiente cuando los pesos no son negativos, y es uno de los algoritmos más usados del mundo. Para los casos que Dijkstra no cubre están Bellman-Ford, Floyd-Warshall y A*.

Lo que vas a aprender

Qué es un grafo ponderado y el problema del camino mínimo.
El algoritmo de Dijkstra paso a paso y con cola de prioridad.
Por qué Dijkstra falla con pesos negativos.
Bellman-Ford y la detección de ciclos negativos.
Floyd-Warshall para todas las parejas de nodos.
La idea de A* con una heurística.

Fundamentos teóricos

El problema

Un grafo ponderado tiene un peso (distancia, tiempo, coste) en cada arista. El camino mínimo entre dos nodos es el de menor suma de pesos. Sin pesos (o con todos iguales), basta con un recorrido en anchura, como en el simulador de recorridos de grafos.

La idea de Dijkstra

Se mantiene una distancia provisional

d[v]

a cada nodo, empezando con

d[\text{origen}] = 0

e infinito para el resto. En cada paso:

Se elige el nodo no visitado con menor $d$ . Su distancia ya es definitiva.
Se relaja cada arista $(u, v)$ que sale de él: si $d[u] + w(u, v) < d[v]$ , se actualiza $d[v]$ y se apunta que se llega a $v$ desde $u$ .
Se repite hasta visitar todos los nodos (o el destino).

Es un algoritmo voraz: en cada paso fija el nodo más cercano. Funciona porque, con pesos no negativos, ningún camino que pase por nodos más lejanos puede mejorar esa distancia.

Implementación con cola de prioridad

import heapq

def dijkstra(grafo, origen):
    dist = {v: float("inf") for v in grafo}
    previo = {v: None for v in grafo}
    dist[origen] = 0
    cola = [(0, origen)]                      # montículo de (distancia, nodo)
    while cola:
        d, u = heapq.heappop(cola)
        if d > dist[u]:
            continue                          # entrada antigua, ya mejorada
        for v, w in grafo[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                previo[v] = u
                heapq.heappush(cola, (dist[v], v))
    return dist, previo

Con un montículo binario, el coste es

O((V + E)\log V)

. Con un array en lugar de montículo,

O(V^2)

, que es mejor para grafos muy densos. Para recuperar el camino se sigue previo desde el destino hasta el origen.

Pesos negativos

Dijkstra no funciona con pesos negativos: puede fijar un nodo cuya distancia luego mejoraría un camino con una arista negativa. Y si hay un ciclo de peso negativo, el camino mínimo ni siquiera existe (se podría dar vueltas para bajar el coste sin fin).

Bellman-Ford

Relaja todas las aristas

V - 1

veces:

def bellman_ford(nodos, aristas, origen):
    dist = {v: float("inf") for v in nodos}
    dist[origen] = 0
    for _ in range(len(nodos) - 1):
        for u, v, w in aristas:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in aristas:                   # una pasada más
        if dist[u] + w < dist[v]:
            raise ValueError("Hay un ciclo negativo")
    return dist

Coste

O(V\,E)

, más lento que Dijkstra, pero admite pesos negativos y detecta ciclos negativos. Lo usaba el protocolo de enrutamiento RIP.

Floyd-Warshall

Calcula las distancias entre todos los pares de nodos con programación dinámica: permite usar como intermedios los nodos

1, 2, \dots, k

poco a poco.

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Coste

O(V^3)

. Muy simple y práctico para grafos de unos pocos cientos de nodos.

A*

Dijkstra explora en todas direcciones. A* prioriza los nodos con menor

d[v] + h(v)

, donde

h

es una heurística que estima la distancia restante al destino (por ejemplo, la distancia en línea recta en un mapa). Si

h

nunca sobreestima, A* encuentra el camino óptimo explorando muchos menos nodos. Se usa en videojuegos y navegadores.

Comparación

Algoritmo	Problema	Pesos negativos	Coste
BFS	Desde un origen, sin pesos	—	$O(V + E)$
Dijkstra	Desde un origen	No	$O((V + E)\log V)$
Bellman-Ford	Desde un origen	Sí, y detecta ciclos	$O(V\,E)$
Floyd-Warshall	Todos los pares	Sí (sin ciclos negativos)	$O(V^3)$
A*	Origen a destino con heurística	No	Depende de $h$

Ejemplos resueltos

Ejemplo 1 · Dijkstra paso a paso

Aristas (no dirigidas): A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2. Origen: A.

Paso	Se fija	B	C	D	E
0		∞	∞	∞	∞
1	A	4	2	∞	∞
2	C	3	2	10	12
3	B	3	2	8	12
4	D	3	2	8	10
5	E	3	2	8	10

Camino mínimo a E: A → C → B → D → E, de coste

2 + 1 + 5 + 2 = 10

Ejemplo 2 · Por qué falla con pesos negativos

Aristas dirigidas: A→B 2, A→C 3, C→B −2. Dijkstra fija B con distancia 2 en el primer paso. Después, el camino A→C→B cuesta

3 - 2 = 1

, pero B ya estaba fijado: el resultado es incorrecto. Bellman-Ford da 1.

Ejemplo 3 · Floyd-Warshall

Con 3 nodos y

d = \begin{pmatrix} 0 & 4 & 11 \\ 6 & 0 & 2 \\ 3 & \infty & 0 \end{pmatrix}

(dirigido):Pasando por el nodo 2:

d[1][3] = \min(11, 4 + 2) = 6

. Pasando por el 3:

d[2][1] = \min(6, 2 + 3) = 5

d[3][2] = \min(\infty, 3 + 4) = 7

.Resultado:

\begin{pmatrix} 0 & 4 & 6 \\ 5 & 0 & 2 \\ 3 & 7 & 0 \end{pmatrix}

Ejemplo 4 · ¿Cuál elijo?

Mapa de carreteras, ruta entre dos ciudades: Dijkstra o A*.
Tabla de distancias entre las 50 capitales de provincia: Floyd-Warshall.
Grafo de tipos de cambio entre monedas (con logaritmos negativos) para buscar arbitraje: Bellman-Ford, que detecta el ciclo negativo.

Errores frecuentes

Usar Dijkstra con pesos negativos.
No descartar las entradas antiguas de la cola de prioridad, que tienen distancias ya mejoradas.
Parar Bellman-Ford sin la última pasada, que es la que detecta ciclos negativos.
Poner el bucle de $k$ por dentro en Floyd-Warshall. Tiene que ser el exterior.
Usar una heurística que sobreestima en A*: deja de garantizar el camino óptimo.

Preguntas frecuentes

¿Cómo calcula Google Maps las rutas tan rápido?

Con un mapa de millones de cruces, Dijkstra puro sería lento. Se preprocesa el grafo (contraction hierarchies, transit nodes) para que cada consulta explore solo unos pocos miles de nodos, y se combina con datos de tráfico en tiempo real.

¿Qué tiene que ver con las redes de ordenadores?

El protocolo OSPF, que usan los routers dentro de una red grande, ejecuta Dijkstra en cada router con el mapa completo de la red. Se explica en el tema de redes de computadores.

Temas relacionados

Recorridos de grafos

BFS y DFS animados.

Montículos

La cola de prioridad de Dijkstra.

Programación dinámica

La idea detrás de Floyd-Warshall.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Algoritmo de Dijkstra y caminos mínimos: Bellman-Ford, Floyd-Warshall y A*

Abrir el simulador

Lo que vas a aprender

Fundamentos teóricos

El problema

La idea de Dijkstra

Implementación con cola de prioridad

Pesos negativos

Bellman-Ford

Floyd-Warshall

A*

Comparación

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados

Recorridos de grafos

Montículos

Programación dinámica

Abrir el simulador

​Lo que vas a aprender

​Fundamentos teóricos

​El problema

​La idea de Dijkstra

​Implementación con cola de prioridad

​Pesos negativos

​Bellman-Ford

​Floyd-Warshall

​A*

​Comparación

​Ejemplos resueltos

​Errores frecuentes

​Preguntas frecuentes

​Temas relacionados

Recorridos de grafos

Montículos

Programación dinámica

Lo que vas a aprender

Fundamentos teóricos

El problema

La idea de Dijkstra

Implementación con cola de prioridad

Pesos negativos

Bellman-Ford

Floyd-Warshall

A*

Comparación

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados