Exercici 5 · Matemática Discreta UAB 2023

a. Diferencieu el problema del camí mínim d'origen únic (resoluble mitjançant Dijkstra) del problema de l'arbre d'extensió mínim (resoluble mitjançant Kruskal o Prim).

Solución: El problema del camí mínim d'origen únic cerca minimitzar la suma dels pesos de les arestes al llarg d'un camí des d'un vèrtex origen fix fins a cadascun dels altres vèrtexs. En canvi, el problema de l'arbre d'extensió mínim (MST) busca un subarbre que connecti tots els vèrtexs del graf minimitzant la suma global del pes de totes les seves arestes; no optimitza distàncies particulars entre parells de vèrtexs.

b. Expliqueu breument per què l'algorisme de Dijkstra pot fallar si el graf conté arestes amb pesos estrictament negatius.

Solución: L'algorisme de Dijkstra és un algorisme voraç (greedy) que assumeix que un cop un vèrtex s'ha marcat com a visitat (o tancat), la distància acumulada des de l'origen és òptima i no es pot reduir posteriorment. Si hi ha arestes negatives, explorar un camí més llarg en nombre d'arestes podria reduir el cost total més endavant, invalidant la decisió voraç i produint resultats incorrectes.