Exercici 4 · Matemática Discreta UAB 2023

a. Expliqueu el funcionament bàsic de l'algorisme de Floyd-Warshall per trobar els camins mínims entre tots els parells de vèrtexs.

Solución: L'algorisme de Floyd-Warshall és un mètode de programació dinàmica que calcula les distàncies mínimes entre qualsevol parell de vèrtexs $i, j \in V$ d'un graf ponderat sense cicles de cost negatiu. Comença amb la matriu de costos directes $D^{(0)}$, on $D_{ij}^{(0)} = w(i, j)$ si existeix l'aresta $(i, j)$, $D_{ii}^{(0)} = 0$, i $\infty$ en cas contrari.

b. Descriviu com s'actualitza la matriu de distàncies $D^{(k)}$ en cada iteració $k$ i com es pot detectar l'existència de cicles de pes negatiu.

Solución: A cada pas $k$ (de 1 a $n$), es permet utilitzar el vèrtex $k$ com a vèrtex intermedi. La matriu s'actualitza segons la recurrència: $$D_{ij}^{(k)} = \min\left(D_{ij}^{(k-1)}, D_{ik}^{(k-1)} + D_{kj}^{(k-1)}\right)$$ Es detecta un cicle de pes negatiu si en qualsevol moment o en la matriu final algun element de la diagonal principal esdevé negatiu ($D_{ii} < 0$).