El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algorismes de Camins Mínims

Següent ►
►

BFS ens va donar el camí amb menys arestes, però comptar arestes és com mesurar un viatge en nombre de carreteres en lloc de en quilòmetres. Tan bon punt cada aresta té un pes —a TaskFlow, les hores o el cost de la transició entre dues tasques— "menys salts" deixa de significar "més barat". Aquesta lliçó presenta els tres algorismes clàssics de camins mínims: Dijkstra (el cavall de batalla, construït sobre el heapq del mòdul 4: la reutilització estrella del curs), Bellman-Ford (més lent però tolerant amb pesos negatius) i Floyd-Warshall (tots contra tots). Continuem sobre la classe Graf, que ja desava pesos des de la 07-02 sense que els féssim servir.

Contingut

  1. Grafs ponderats a TaskFlow
  2. Per què BFS no basta amb pesos
  3. Dijkstra: la idea i la seva cua de prioritat
  4. Implementació completa amb predecessors
  5. Traça pas a pas amb taula de distàncies
  6. La limitació de Dijkstra: pesos negatius
  7. Bellman-Ford: idea i codi compacte
  8. Floyd-Warshall: tots-a-tots (menció)
  9. Taula comparativa i elecció

Grafs ponderats a TaskFlow

Imaginem la planificació entre dues fites del projecte: des de la fita inici fins a llancament hi ha rutes alternatives (fer prototip o anar directes al disseny, sortir per l'API o per la UI), i cada transició té un cost en hores. L'equip vol la ruta més barata entre les dues fites:

pla = Graf(dirigit=True)
pla.afegir_aresta("inici", "dissenyar", 4)
pla.afegir_aresta("inici", "prototip", 2)
pla.afegir_aresta("prototip", "dissenyar", 1)
pla.afegir_aresta("prototip", "ui", 8)
pla.afegir_aresta("dissenyar", "ui", 3)
pla.afegir_aresta("dissenyar", "api", 5)
pla.afegir_aresta("api", "llancament", 2)
pla.afegir_aresta("ui", "llancament", 2)
graph LR
    I[inici] -->|4| D[dissenyar]
    I -->|2| P[prototip]
    P -->|1| D
    P -->|8| U[ui]
    D -->|3| U
    D -->|5| A[api]
    A -->|2| L[llancament]
    U -->|2| L

Per què BFS no basta amb pesos

BFS diria que el millor camí inici → llancament és qualsevol de 3 arestes, per exemple inici → dissenyar → api → llancament, amb cost real 4 + 5 + 2 = 11 hores. Però el camí de 4 arestes inici → prototip → dissenyar → ui → llancament costa 2 + 1 + 3 + 2 = 8 hores: més salts, menys cost. BFS optimitza el nombre d'arestes perquè processa els vèrtexs per capes; amb pesos, la capa no diu res del cost. Necessitem processar els vèrtexs per cost acumulat, no per distància en salts. I quina estructura lliura sempre "el de menor valor primer"? La cua de prioritat del mòdul 4.

Dijkstra: la idea i la seva cua de prioritat

Dijkstra manté, per a cada vèrtex, la millor distància coneguda des de l'origen, i repeteix un bucle cobdiciós:

  1. Pren el vèrtex no tancat amb menor distància coneguda (això ho dóna el monticle en O(log n)).
  2. Tanca'l: la seva distància ja és definitiva.
  3. Relaxa les seves arestes: per a cada veí, si passar pel vèrtex acabat de tancar millora la seva distància, apunta la millora (i el predecessor).

Per què pot "tancar" amb tanta seguretat? Perquè si tots els pesos són ≥ 0, qualsevol altre camí fins a aquell vèrtex passaria per vèrtexs més llunyans i ja no pot millorar. Aquesta és exactament la hipòtesi que es trenca amb pesos negatius, com veurem.

En lloc d'una operació "decrementar clau" (que heapq no ofereix), fem servir el truc estàndard: inserir entrades duplicades i descartar les obsoletes en extreure-les — la mateixa filosofia de tuples (prioritat, dada) de la SafataUrgencies del mòdul 4.

Implementació completa amb predecessors

import heapq

def dijkstra(graf, origen):
    """Distàncies mínimes des d'origen i predecessors per reconstruir camins."""
    distancies = {v: float("inf") for v in graf.vertexs()}
    distancies[origen] = 0
    predecessor = {origen: None}
    monticle = [(0, origen)]             # tuples (distancia, vertex), mòdul 4
    tancats = set()

    while monticle:
        dist, actual = heapq.heappop(monticle)    # el més barat conegut
        if actual in tancats:
            continue                      # entrada obsoleta: ja es va tancar abans
        tancats.add(actual)
        for vei, pes in graf.veins(actual).items():
            nova = dist + pes
            if nova < distancies[vei]:            # millora passar per 'actual'?
                distancies[vei] = nova
                predecessor[vei] = actual
                heapq.heappush(monticle, (nova, vei))
    return distancies, predecessor

def reconstruir_cami(predecessor, desti):
    """Segueix els predecessors cap enrere i capgira el resultat al final."""
    if desti not in predecessor:
        return None                       # inabastable des de l'origen
    cami = []
    while desti is not None:
        cami.append(desti)
        desti = predecessor[desti]
    return cami[::-1]

distancies, predecessor = dijkstra(pla, "inici")
print(distancies["llancament"])                          # 8
print(reconstruir_cami(predecessor, "llancament"))
# ['inici', 'prototip', 'dissenyar', 'ui', 'llancament']

Punts clau del codi:

  • distancies arrenca a infinit (float("inf")) llevat de l'origen: "encara no conec cap camí". Tot vèrtex inabastable acaba l'algorisme amb infinit.
  • L'if actual in tancats: continue és el descart de duplicats: un vèrtex pot ser diverses vegades al monticle amb distàncies diferents; només la primera extracció (la menor) compta.
  • predecessor[v] desa des d'on es va arribar a v pel millor camí; reconstruir_cami el recorre cap enrere — per això cal invertir la llista al final ([::-1]), igual que quan buidàvem una pila al mòdul 3.
  • Cost: cada aresta pot inserir una entrada al monticle, així que O((n + a) · log n) — per a grafs dispersos, gairebé lineal.

Traça pas a pas amb taula de distàncies

Cada fila mostra el vèrtex que es tanca i les distàncies després de relaxar les seves arestes (en negreta les que milloren):

Es tanca inici prototip dissenyar ui api llancament
(inicial) 0 inf inf inf inf inf
inici (0) 0 2 4 inf inf inf
prototip (2) 0 2 3 10 inf inf
dissenyar (3) 0 2 3 6 8 inf
ui (6) 0 2 3 6 8 8
api (8) 0 2 3 6 8 8
llancament (8) — — — — — —

Lectura dels moments clau:

  • En tancar prototip, la distància de dissenyar millora de 4 a 3: la ruta indirecta inici → prototip → dissenyar (2+1) guanya la directa (4). El predecessor de dissenyar passa d'inici a prototip. Això és la relaxació en acció.
  • En tancar dissenyar, ui millora de 10 (via prototip) a 6 (via dissenyar).
  • llancament queda a 8 via ui; quan després es tanca api, la seva oferta (8 + 2 = 10) ja no millora res.
  • Al monticle queden entrades obsoletes — (4, dissenyar), (10, ui), (10, llancament) — que el continue descarta en sortir.

La limitació de Dijkstra: pesos negatius

Dijkstra tanca vèrtexs assumint que allunyar-se mai no abarateix. Amb una aresta negativa, aquesta lògica es trenca: un camí que primer "s'allunya" podria després descomptar cost i superar el que vam donar per definitiu — però el vèrtex ja està tancat i no es revisa. Resultat: respostes incorrectes sense cap avís, el pitjor tipus d'error.

Pesos negatius a la vida real? A TaskFlow podrien modelar transicions que estalvien (reutilitzar feina feta: fer B just després d'A descompta hores); en finances, operacions amb benefici; en logística, trams subvencionats. Quan n'hi hagi, l'algorisme honest és Bellman-Ford.

Bellman-Ford: idea i codi compacte

Bellman-Ford renuncia a l'astúcia del monticle i aplica força bruta ordenada: relaxar totes les arestes, n − 1 vegades. Després de la passada k, són correctes totes les distàncies de camins mínims amb ≤ k arestes; com que cap camí simple no en té més de n − 1, amb això n'hi ha prou. I regala una cosa que Dijkstra no pot: si en una passada extra encara millora alguna cosa, hi ha un cicle de pes negatiu (un bucle que abarateix sense fi, amb el qual "camí mínim" deixa de tenir sentit).

def bellman_ford(graf, origen):
    # llista d'arestes (la tercera representació, esmentada a la 07-02)
    arestes = [(u, v, p) for u in graf.vertexs()
                          for v, p in graf.veins(u).items()]
    distancies = {v: float("inf") for v in graf.vertexs()}
    distancies[origen] = 0
    predecessor = {origen: None}

    for _ in range(len(distancies) - 1):     # n - 1 passades
        canvi = False
        for u, v, p in arestes:              # relaxar TOTES les arestes
            if distancies[u] + p < distancies[v]:
                distancies[v] = distancies[u] + p
                predecessor[v] = u
                canvi = True
        if not canvi:                        # res no millora: acabar abans
            break

    for u, v, p in arestes:                  # passada extra: encara millora res?
        if distancies[u] + p < distancies[v]:
            raise ValueError("Cicle de pes negatiu: no hi ha camins mínims")
    return distancies, predecessor

Cost: O(n · a) — sensiblement pitjor que Dijkstra, i aquest és el tracte: robustesa a canvi de velocitat. Fixa't que reutilitza reconstruir_cami tal qual: la interfície (distàncies + predecessors) és la mateixa.

Floyd-Warshall: tots-a-tots (menció)

Quan la pregunta no és "des d'aquest origen" sinó "entre tots els parells" (una taula de costos de qualsevol fita a qualsevol fita), l'algorisme de referència és Floyd-Warshall: programació dinàmica sobre la matriu de distàncies, provant cada vèrtex k com a escala intermèdia:

# esquema: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) per a tot k, i, j
Tret Valor
Resultat Matriu n × n de distàncies tots-a-tots
Cost O(n³) en temps, O(n²) en espai
Pesos negatius Sí (sense cicles negatius; els detecta a la diagonal)
Representació natural Matriu d'adjacència — el seu retorn anunciat a la 07-02

Tres bucles imbricats i una línia de relaxació: probablement l'algorisme més curt del curs pel resultat que produeix. Només compensa amb grafs petits o quan de debò es necessita la taula completa; no el desenvoluparem més.

Taula comparativa i elecció

Dijkstra Bellman-Ford Floyd-Warshall
Pregunta 1 origen → tots 1 origen → tots tots → tots
Cost O((n + a) log n) O(n · a) O(n³)
Pesos negatius No Sí Sí
Detecta cicles negatius No Sí Sí
Estructura de suport heapq (mòdul 4) Llista d'arestes Matriu (07-02)
Fes-lo servir quan... Pesos ≥ 0 (el cas normal) Hi pot haver pesos negatius Graf petit, taula completa

Regla pràctica: Dijkstra per defecte; Bellman-Ford si els pesos poden ser negatius; Floyd-Warshall si necessites la matriu completa i n és modest (centenars, no centenars de milers).

Errors Comuns i Consells

  • Executar Dijkstra amb pesos negatius. No falla ni avisa: simplement retorna distàncies incorrectes. Si els teus pesos poden ser negatius, valida abans o canvia d'algorisme.
  • Oblidar el descart d'entrades obsoletes (if actual in tancats: continue). L'algorisme relaxaria vèrtexs ja tancats des d'entrades velles del monticle: resultats de vegades correctes, de vegades no — el pitjor tipus de bug.
  • Posar al monticle tuples no comparables. Si en comptes d'ids hi posessis els dict de tasca, heapq fallaria en desempatar tuples amb la mateixa distància. És exactament el problema que vam resoldre al mòdul 4 amb (prioritat, comptador, tasca); aquí els ids (strings) són comparables i n'hi ha prou amb (distancia, id).
  • Reconstruir el camí oblidant invertir-lo: els predecessors es recorren del destí cap a l'origen; sense el [::-1] final, el camí surt del revés.
  • Confondre "no hi ha camí" amb "distància enorme": comprova distancies[v] == float("inf") explícitament abans de fer servir el valor.
  • Consell: desa sempre els predecessors. La distància diu quant costa; el camí reconstruït diu què fer, i en una aplicació real (TaskFlow inclòs) és el que l'usuari vol veure.

Exercicis

Exercici 1: llegir els resultats de Dijkstra

Amb distancies i predecessor calculats sobre pla des d'inici: (a) quina és la ruta més barata fins a api i el seu cost? (b) Afegeix l'aresta pla.afegir_aresta("prototip", "api", 4) i raona (sense executar) com canvien la distància i el predecessor d'api.

Exercici 2: cost d'una ruta concreta

Escriu cost_cami(graf, cami) que retorni el cost total d'una llista de vèrtexs consecutius, o None si algun tram no existeix com a aresta. Compara el cost de ["inici", "dissenyar", "api", "llancament"] amb l'òptim de Dijkstra.

Exercici 3: un descompte perillós

Suposa que fer ui just després d'api reutilitza components: aresta api → ui amb pes −4. (a) Continua sent vàlid Dijkstra? (b) Executa mentalment Bellman-Ford: canvia la distància de llancament? (c) Què passaria si el descompte fos ui → prototip amb pes −7?

Solucions

Solució 1:

  • (a) reconstruir_cami(predecessor, "api") → ['inici', 'prototip', 'dissenyar', 'api'], cost 2 + 1 + 5 = 8. Observa que comparteix prefix amb la ruta a llancament: els camins mínims des d'un origen formen un arbre (l'arbre de camins mínims), un altre retrobament amb el mòdul 6.
  • (b) La nova oferta per a api seria 2 + 4 = 6 < 8: en tancar prototip, api quedaria a 6 amb predecessor prototip. A més llancament rebria l'oferta 6 + 2 = 8: mateix cost total per una altra ruta; com que 8 no és menor que 8, la relaxació no canvia el predecessor i es conserva la ruta per ui.

Solució 2:

def cost_cami(graf, cami):
    total = 0
    for origen, desti in zip(cami, cami[1:]):   # parells consecutius
        if not graf.existeix_aresta(origen, desti):
            return None
        total += graf.veins(origen)[desti]
    return total

print(cost_cami(pla, ["inici", "dissenyar", "api", "llancament"]))  # 11
print(distancies["llancament"])                                     # 8

zip(cami, cami[1:]) aparella cada vèrtex amb el següent: la manera idiomàtica de recórrer trams. La ruta "directa" costa 11 davant de l'òptim de 8: un 37 % més cara per estalviar-se una aresta.

Solució 3:

  • (a) No: amb una aresta negativa al graf, la garantia de tancament de Dijkstra desapareix (encara que en algun cas concret l'encerti, ja no és fiable).
  • (b) Amb api → ui = −4: arribar a ui via api costa 8 + (−4) = 4 < 6, i llavors llancament baixa a 4 + 2 = 6. Bellman-Ford ho troba en passades successives; la resposta canvia de 8 a 6, amb ruta inici → prototip → dissenyar → api → ui → llancament.
  • (c) ui → prototip = −7 crearia el cicle prototip → dissenyar → ui → prototip de pes 1 + 3 − 7 = −3: cada volta "estalvia" 3 hores, les distàncies caurien sense fons i Bellman-Ford llançaria el ValueError de cicle negatiu. Un bon recordatori que un model amb descomptes il·limitats és un model mal plantejat.

Conclusió

Amb pesos a les arestes, BFS cedeix el lloc a Dijkstra: la cua de prioritat heapq del mòdul 4 lliura sempre el vèrtex més barat, la relaxació millora distàncies i predecessors, i reconstruir_cami converteix el resultat en una ruta accionable — tot en O((n + a) log n). Bellman-Ford cobreix el terreny que Dijkstra no trepitja (pesos negatius, cicles negatius) a canvi d'O(n · a), i Floyd-Warshall respon el tots-a-tots en O(n³). Fins ara sempre hem minimitzat el cost d'una ruta entre dos punts. La propera lliçó canvia la pregunta: no anar d'A a B, sinó connectar tots els punts entre si amb el mínim cost total — l'arbre d'expansió mínima, on reapareixen els grafs no dirigits, Prim (gairebé un Dijkstra disfressat) i una estructura nova: Union-Find.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats