Exercici 5 · Matemática Discreta UAB 2025

Exercici 5 (3 punts). Algorisme de Dijkstra i recorreguts

La taula següent reflecteix l'evolució de l'algorisme de Dijkstra per calcular les distàncies mínimes des del vèrtex origen $A$:

Pas

$d(A)$

$d(B)$

$d(C)$

$d(D)$

$d(E)$

$d(F)$

$d(G)$

Pivot/Visitat

0 · 0 · $\infty$ · $\infty$ · $\infty$ · $\infty$ · $\infty$ · $\infty$ · $A$

1 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 27 · $F$

2 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 27 · $E$

3 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 16 · $G$

4 · 0 · 18 · $\infty$ · $\infty$ · 2 · 1 · 16 · $B$

5 · 0 · 18 · 19 · $\infty$ · 2 · 1 · 16 · $C$

6 · 0 · 18 · 19 · 48 · 2 · 1 · 16 · $D$

a.

Recupereu el camí de cost mínim des d'$A$ fins a $D$ i indiqueu el seu cost total.

b.

Un estudiant sosté que al graf original hi ha una aresta directa $(A, G)$ de cost 10. És compatible aquesta afirmació amb la taula? Raoneu la resposta.

Sí

No

c.

Construïu l'arbre de camins mínims amb origen a $A$ i especifiqueu el predecessor de cada vèrtex.

Predecessor de $B$:

Predecessor de $C$:

Predecessor de $D$:

Predecessor de $E$:

Predecessor de $F$:

Predecessor de $G$:

d.

Prenent com a base l'arbre de camins mínims de l'apartat anterior, escriviu un recorregut en amplada (BFS) i un recorregut en profunditat (DFS) començant des d'$A$. En cas d'haver d'escollir entre diversos veïns, processeu-los en ordre alfabètic.

e.

Suposeu que el cost de l'aresta $(B, C)$ s'incrementa d'1 a 10. Sense necessitat d'executar novament tot l'algorisme de Dijkstra, indiqueu quins vèrtexs poden veure incrementada la seva distància mínima respecte a $A$.