El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Algoritmos de Caminos Mínimos

Siguiente ►
►

BFS nos dio el camino con menos aristas, pero contar aristas es como medir un viaje en número de carreteras en lugar de en kilómetros. En cuanto cada arista tiene un peso —en TaskFlow, las horas o el coste de la transición entre dos tareas— "menos saltos" deja de significar "más barato". Esta lección presenta los tres algoritmos clásicos de caminos mínimos: Dijkstra (el caballo de batalla, construido sobre el heapq del módulo 4: la reutilización estrella del curso), Bellman-Ford (más lento pero tolerante con pesos negativos) y Floyd-Warshall (todos contra todos). Seguimos sobre la clase Grafo, que ya guardaba pesos desde 07-02 sin que los usáramos.

Contenido

  1. Grafos ponderados en TaskFlow
  2. Por qué BFS no basta con pesos
  3. Dijkstra: la idea y su cola de prioridad
  4. Implementación completa con predecesores
  5. Traza paso a paso con tabla de distancias
  6. La limitación de Dijkstra: pesos negativos
  7. Bellman-Ford: idea y código compacto
  8. Floyd-Warshall: todos-a-todos (mención)
  9. Tabla comparativa y elección

Grafos ponderados en TaskFlow

Imaginemos la planificación entre dos hitos del proyecto: desde el hito inicio hasta lanzamiento hay rutas alternativas (hacer prototipo o ir directos al diseño, salir por la API o por la UI), y cada transición tiene un coste en horas. El equipo quiere la ruta más barata entre los dos hitos:

plan = Grafo(dirigido=True)
plan.anadir_arista("inicio", "disenar", 4)
plan.anadir_arista("inicio", "prototipo", 2)
plan.anadir_arista("prototipo", "disenar", 1)
plan.anadir_arista("prototipo", "ui", 8)
plan.anadir_arista("disenar", "ui", 3)
plan.anadir_arista("disenar", "api", 5)
plan.anadir_arista("api", "lanzamiento", 2)
plan.anadir_arista("ui", "lanzamiento", 2)
graph LR
    I[inicio] -->|4| D[disenar]
    I -->|2| P[prototipo]
    P -->|1| D
    P -->|8| U[ui]
    D -->|3| U
    D -->|5| A[api]
    A -->|2| L[lanzamiento]
    U -->|2| L

Por qué BFS no basta con pesos

BFS diría que el mejor camino inicio → lanzamiento es cualquiera de 3 aristas, por ejemplo inicio → disenar → api → lanzamiento, con coste real 4 + 5 + 2 = 11 horas. Pero el camino de 4 aristas inicio → prototipo → disenar → ui → lanzamiento cuesta 2 + 1 + 3 + 2 = 8 horas: más saltos, menos coste. BFS optimiza el número de aristas porque procesa los vértices por capas; con pesos, la capa no dice nada del coste. Necesitamos procesar los vértices por coste acumulado, no por distancia en saltos. ¿Y qué estructura entrega siempre "el de menor valor primero"? La cola de prioridad del módulo 4.

Dijkstra: la idea y su cola de prioridad

Dijkstra mantiene, para cada vértice, la mejor distancia conocida desde el origen, y repite un bucle codicioso:

  1. Toma el vértice no cerrado con menor distancia conocida (eso lo da el montículo en O(log n)).
  2. Ciérralo: su distancia ya es definitiva.
  3. Relaja sus aristas: para cada vecino, si pasar por el vértice recién cerrado mejora su distancia, apunta la mejora (y el predecesor).

¿Por qué puede "cerrar" con tanta seguridad? Porque si todos los pesos son ≥ 0, cualquier otro camino hasta ese vértice pasaría por vértices más lejanos y ya no puede mejorar. Esta es exactamente la hipótesis que se rompe con pesos negativos, como veremos.

En lugar de una operación "decrementar clave" (que heapq no ofrece), usamos el truco estándar: insertar entradas duplicadas y descartar las obsoletas al extraerlas — la misma filosofía de tuplas (prioridad, dato) de la BandejaUrgencias del módulo 4.

Implementación completa con predecesores

import heapq

def dijkstra(grafo, origen):
    """Distancias mínimas desde origen y predecesores para reconstruir caminos."""
    distancias = {v: float("inf") for v in grafo.vertices()}
    distancias[origen] = 0
    predecesor = {origen: None}
    monticulo = [(0, origen)]            # tuplas (distancia, vertice), módulo 4
    cerrados = set()

    while monticulo:
        dist, actual = heapq.heappop(monticulo)   # el más barato conocido
        if actual in cerrados:
            continue                      # entrada obsoleta: ya se cerró antes
        cerrados.add(actual)
        for vecino, peso in grafo.vecinos(actual).items():
            nueva = dist + peso
            if nueva < distancias[vecino]:        # ¿mejora pasar por 'actual'?
                distancias[vecino] = nueva
                predecesor[vecino] = actual
                heapq.heappush(monticulo, (nueva, vecino))
    return distancias, predecesor

def reconstruir_camino(predecesor, destino):
    """Sigue los predecesores hacia atrás y da la vuelta al final."""
    if destino not in predecesor:
        return None                       # inalcanzable desde el origen
    camino = []
    while destino is not None:
        camino.append(destino)
        destino = predecesor[destino]
    return camino[::-1]

distancias, predecesor = dijkstra(plan, "inicio")
print(distancias["lanzamiento"])                          # 8
print(reconstruir_camino(predecesor, "lanzamiento"))
# ['inicio', 'prototipo', 'disenar', 'ui', 'lanzamiento']

Puntos clave del código:

  • distancias arranca en infinito (float("inf")) salvo el origen: "aún no conozco camino". Todo vértice inalcanzable termina el algoritmo con infinito.
  • El if actual in cerrados: continue es el descarte de duplicados: un vértice puede estar varias veces en el montículo con distancias distintas; solo la primera extracción (la menor) cuenta.
  • predecesor[v] guarda desde dónde se llegó a v por el mejor camino; reconstruir_camino lo recorre hacia atrás — por eso hace falta invertir la lista al final ([::-1]), igual que cuando vaciábamos una pila en el módulo 3.
  • Coste: cada arista puede insertar una entrada en el montículo, así que O((n + a) · log n) — para grafos dispersos, casi lineal.

Traza paso a paso con tabla de distancias

Cada fila muestra el vértice que se cierra y las distancias tras relajar sus aristas (en negrita las que mejoran):

Se cierra inicio prototipo disenar ui api lanzamiento
(inicial) 0 inf inf inf inf inf
inicio (0) 0 2 4 inf inf inf
prototipo (2) 0 2 3 10 inf inf
disenar (3) 0 2 3 6 8 inf
ui (6) 0 2 3 6 8 8
api (8) 0 2 3 6 8 8
lanzamiento (8) — — — — — —

Lectura de los momentos clave:

  • Al cerrar prototipo, la distancia de disenar mejora de 4 a 3: la ruta indirecta inicio → prototipo → disenar (2+1) gana a la directa (4). El predecesor de disenar pasa de inicio a prototipo. Esto es la relajación en acción.
  • Al cerrar disenar, ui mejora de 10 (vía prototipo) a 6 (vía disenar).
  • lanzamiento queda en 8 vía ui; cuando después se cierra api, su oferta (8 + 2 = 10) ya no mejora nada.
  • En el montículo quedan entradas obsoletas — (4, disenar), (10, ui), (10, lanzamiento) — que el continue descarta al salir.

La limitación de Dijkstra: pesos negativos

Dijkstra cierra vértices asumiendo que alejarse nunca abarata. Con una arista negativa, esa lógica se rompe: un camino que primero "se aleja" podría luego descontar coste y superar al que dimos por definitivo — pero el vértice ya está cerrado y no se revisa. Resultado: respuestas incorrectas sin ningún aviso, el peor tipo de error.

¿Pesos negativos en la vida real? En TaskFlow podrían modelar transiciones que ahorran (reutilizar trabajo hecho: hacer B justo después de A descuenta horas); en finanzas, operaciones con beneficio; en logística, tramos subvencionados. Cuando existan, el algoritmo honesto es Bellman-Ford.

Bellman-Ford: idea y código compacto

Bellman-Ford renuncia a la astucia del montículo y aplica fuerza bruta ordenada: relajar todas las aristas, n − 1 veces. Tras la pasada k, son correctas todas las distancias de caminos mínimos con ≤ k aristas; como ningún camino simple tiene más de n − 1, con eso basta. Y regala algo que Dijkstra no puede: si en una pasada extra todavía mejora algo, hay un ciclo de peso negativo (un bucle que abarata sin fin, con el que "camino mínimo" deja de tener sentido).

def bellman_ford(grafo, origen):
    # lista de aristas (la tercera representación, mencionada en 07-02)
    aristas = [(u, v, p) for u in grafo.vertices()
                          for v, p in grafo.vecinos(u).items()]
    distancias = {v: float("inf") for v in grafo.vertices()}
    distancias[origen] = 0
    predecesor = {origen: None}

    for _ in range(len(distancias) - 1):     # n - 1 pasadas
        cambio = False
        for u, v, p in aristas:              # relajar TODAS las aristas
            if distancias[u] + p < distancias[v]:
                distancias[v] = distancias[u] + p
                predecesor[v] = u
                cambio = True
        if not cambio:                       # nada mejora: terminar antes
            break

    for u, v, p in aristas:                  # pasada extra: ¿aún mejora algo?
        if distancias[u] + p < distancias[v]:
            raise ValueError("Ciclo de peso negativo: no hay caminos mínimos")
    return distancias, predecesor

Coste: O(n · a) — sensiblemente peor que Dijkstra, y ese es el trato: robustez a cambio de velocidad. Fíjate en que reutiliza reconstruir_camino tal cual: la interfaz (distancias + predecesores) es la misma.

Floyd-Warshall: todos-a-todos (mención)

Cuando la pregunta no es "desde este origen" sino "entre todos los pares" (una tabla de costes de cualquier hito a cualquier hito), el algoritmo de referencia es Floyd-Warshall: programación dinámica sobre la matriz de distancias, probando cada vértice k como escala intermedia:

# esquema: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) para todo k, i, j
Rasgo Valor
Resultado Matriz n × n de distancias todos-a-todos
Coste O(n³) en tiempo, O(n²) en espacio
Pesos negativos Sí (sin ciclos negativos; los detecta en la diagonal)
Representación natural Matriz de adyacencia — su regreso anunciado en 07-02

Tres bucles anidados y una línea de relajación: probablemente el algoritmo más corto del curso por resultado que produce. Solo compensa con grafos pequeños o cuando de verdad se necesita la tabla completa; no lo desarrollaremos más.

Tabla comparativa y elección

Dijkstra Bellman-Ford Floyd-Warshall
Pregunta 1 origen → todos 1 origen → todos todos → todos
Coste O((n + a) log n) O(n · a) O(n³)
Pesos negativos No Sí Sí
Detecta ciclos negativos No Sí Sí
Estructura de apoyo heapq (módulo 4) Lista de aristas Matriz (07-02)
Úsalo cuando... Pesos ≥ 0 (el caso normal) Puede haber pesos negativos Grafo pequeño, tabla completa

Regla práctica: Dijkstra por defecto; Bellman-Ford si los pesos pueden ser negativos; Floyd-Warshall si necesitas la matriz completa y n es modesto (cientos, no cientos de miles).

Errores Comunes y Consejos

  • Ejecutar Dijkstra con pesos negativos. No falla ni avisa: simplemente devuelve distancias incorrectas. Si tus pesos pueden ser negativos, valida antes o cambia de algoritmo.
  • Olvidar el descarte de entradas obsoletas (if actual in cerrados: continue). El algoritmo relajaría vértices ya cerrados desde entradas viejas del montículo: resultados a veces correctos, a veces no — el peor tipo de bug.
  • Meter en el montículo tuplas no comparables. Si en vez de ids metieras los dict de tarea, heapq fallaría al desempatar tuplas con igual distancia. Es exactamente el problema que resolvimos en el módulo 4 con (prioridad, contador, tarea); aquí los ids (strings) son comparables y basta con (distancia, id).
  • Reconstruir el camino olvidando invertirlo: los predecesores se recorren del destino hacia el origen; sin el [::-1] final, el camino sale del revés.
  • Confundir "no hay camino" con "distancia enorme": comprueba distancias[v] == float("inf") explícitamente antes de usar el valor.
  • Consejo: guarda siempre los predecesores. La distancia dice cuánto cuesta; el camino reconstruido dice qué hacer, y en una aplicación real (TaskFlow incluido) es lo que el usuario quiere ver.

Ejercicios

Ejercicio 1: leer los resultados de Dijkstra

Con distancias y predecesor calculados sobre plan desde inicio: (a) ¿cuál es la ruta más barata hasta api y su coste? (b) Añade la arista plan.anadir_arista("prototipo", "api", 4) y razona (sin ejecutar) cómo cambian la distancia y el predecesor de api.

Ejercicio 2: coste de una ruta concreta

Escribe coste_camino(grafo, camino) que devuelva el coste total de una lista de vértices consecutivos, o None si algún tramo no existe como arista. Compara el coste de ["inicio", "disenar", "api", "lanzamiento"] con el óptimo de Dijkstra.

Ejercicio 3: un descuento peligroso

Supón que hacer ui justo después de api reutiliza componentes: arista api → ui con peso −4. (a) ¿Sigue siendo válido Dijkstra? (b) Ejecuta mentalmente Bellman-Ford: ¿cambia la distancia de lanzamiento? (c) ¿Qué pasaría si el descuento fuera ui → prototipo con peso −7?

Soluciones

Solución 1:

  • (a) reconstruir_camino(predecesor, "api") → ['inicio', 'prototipo', 'disenar', 'api'], coste 2 + 1 + 5 = 8. Observa que comparte prefijo con la ruta a lanzamiento: los caminos mínimos desde un origen forman un árbol (el árbol de caminos mínimos), otro reencuentro con el módulo 6.
  • (b) La nueva oferta para api sería 2 + 4 = 6 < 8: al cerrar prototipo, api quedaría en 6 con predecesor prototipo. Además lanzamiento recibiría la oferta 6 + 2 = 8: mismo coste total por otra ruta; como 8 no es menor que 8, la relajación no cambia el predecesor y se conserva la ruta por ui.

Solución 2:

def coste_camino(grafo, camino):
    total = 0
    for origen, destino in zip(camino, camino[1:]):   # pares consecutivos
        if not grafo.existe_arista(origen, destino):
            return None
        total += grafo.vecinos(origen)[destino]
    return total

print(coste_camino(plan, ["inicio", "disenar", "api", "lanzamiento"]))  # 11
print(distancias["lanzamiento"])                                        # 8

zip(camino, camino[1:]) empareja cada vértice con el siguiente: la forma idiomática de recorrer tramos. La ruta "directa" cuesta 11 frente al óptimo de 8: un 37 % más cara por ahorrarse una arista.

Solución 3:

  • (a) No: con una arista negativa en el grafo, la garantía de cierre de Dijkstra desaparece (aunque en algún caso concreto acierte, ya no es fiable).
  • (b) Con api → ui = −4: llegar a ui vía api cuesta 8 + (−4) = 4 < 6, y entonces lanzamiento baja a 4 + 2 = 6. Bellman-Ford lo encuentra en pasadas sucesivas; la respuesta cambia de 8 a 6, con ruta inicio → prototipo → disenar → api → ui → lanzamiento.
  • (c) ui → prototipo = −7 crearía el ciclo prototipo → disenar → ui → prototipo de peso 1 + 3 − 7 = −3: cada vuelta "ahorra" 3 horas, las distancias caerían sin fondo y Bellman-Ford lanzaría el ValueError de ciclo negativo. Un buen recordatorio de que un modelo con descuentos ilimitados es un modelo mal planteado.

Conclusión

Con pesos en las aristas, BFS cede el puesto a Dijkstra: la cola de prioridad heapq del módulo 4 entrega siempre el vértice más barato, la relajación mejora distancias y predecesores, y reconstruir_camino convierte el resultado en una ruta accionable — todo en O((n + a) log n). Bellman-Ford cubre el terreno que Dijkstra no pisa (pesos negativos, ciclos negativos) a cambio de O(n · a), y Floyd-Warshall responde el todos-a-todos en O(n³). Hasta ahora siempre hemos minimizado el coste de una ruta entre dos puntos. La próxima lección cambia la pregunta: no ir de A a B, sino conectar todos los puntos entre sí con el mínimo coste total — el árbol de expansión mínima, donde reaparecen los grafos no dirigidos, Prim (casi un Dijkstra disfrazado) y una estructura nueva: Union-Find.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados