Caminos mínimos: Dijkstra y Bellman-Ford

Con aristas sin peso, BFS da el camino más corto y no hay más que hablar. Apenas las aristas pesan distinto —kilómetros, minutos, costo— la cantidad de saltos deja de importar y hace falta otra cosa. Hay dos algoritmos clásicos, y elegir mal cuesta un orden de magnitud o una respuesta incorrecta.

Relajar una arista: la única operación

Los dos se construyen sobre la misma operación: relajar una arista. Si llegar a $u$ cuesta $d[u]$ y la arista hacia $v$ pesa $w$, y ese total mejora lo conocido, se actualiza:

Se arranca con todas las distancias en infinito salvo el origen en cero, y se guarda de quién vino cada vértice para reconstruir el camino. Lo único que cambia entre algoritmos es en qué orden y cuántas veces se relaja.

Dijkstra, que es goloso

Dijkstra es goloso: entre los vértices todavía no cerrados, toma el de menor distancia tentativa, la da por definitiva y relaja sus aristas salientes.

El argumento es que ese vértice no puede mejorar, porque cualquier otro camino hacia él pasa por un vértice pendiente que ya está más lejos, y agregarle aristas sólo suma. Con una cola de prioridad, el costo es $O((V+E)\log V)$: cada vértice se cierra una vez y cada arista se relaja una vez.

Por qué un peso negativo lo rompe

Ese argumento se apoya en que las aristas no restan. Con un peso negativo, un camino que hoy parece más largo puede abaratarse después, y Dijkstra ya cerró el vértice: la respuesta sale mal, sin avisar.

Y si hay un ciclo de peso negativo alcanzable, el problema directamente no tiene solución: recorrerlo otra vez siempre mejora, y el mínimo es menos infinito. Detectar esa situación es parte del trabajo, no un caso borde.

Bellman-Ford: relajar todo, V-1 veces

Bellman-Ford abandona el orden goloso: relaja todas las aristas, $V-1$ veces. Después de la pasada $k$, están correctas todas las distancias cuyo camino mínimo usa a lo sumo $k$ aristas, y un camino mínimo sin ciclos no puede tener más de $V-1$.

Cuesta $O(V\,E)$, bastante más caro. A cambio, una pasada extra alcanza para detectar el problema: si alguna arista todavía se puede relajar, hay un ciclo negativo alcanzable. Es programación dinámica sobre la cantidad de aristas del camino.

Cuál usar según los pesos

La regla es directa: sin pesos, BFS; con pesos no negativos, Dijkstra; con pesos negativos, Bellman-Ford. Y si el grafo es dirigido y acíclico, hay algo mejor que los tres: relajar en orden topológico resuelve en $O(V+E)$ incluso con negativos.

Vale la pena recordar que los pesos negativos no son un ejercicio artificial: aparecen en arbitraje de monedas, en balances con ingresos y egresos, y en cualquier costo que pueda ser una ganancia.

Dos detalles de implementación

Dos detalles de implementación. En Dijkstra, la cola de prioridad no suele soportar bajar la prioridad de un elemento: lo habitual es insertar el vértice de nuevo con la distancia mejorada e ignorar las entradas viejas al sacarlas. La cola crece hasta $O(E)$, y el costo no cambia.

El segundo: los dos algoritmos calculan distancias desde un solo origen a todos los destinos. Para un destino puntual se puede cortar al cerrarlo, y si hay una estimación de lo que falta —una distancia en línea recta, por ejemplo—, A* usa esa heurística para llegar antes.

Cuál de los tres, y qué los distingue

Cierre

La misma relajación, dos estrategias. Dijkstra la aplica en orden creciente de distancia y cierra cada vértice una vez, rápido pero sólo con pesos no negativos. Bellman-Ford la aplica $V-1$ veces sobre todo el grafo, más caro pero correcto con negativos y capaz de detectar ciclos de peso negativo.