Esercizi - 2.3
Esercizio n. 2.3.1
Si consideri il grafo di figura ai cui archi sono associati dei costi.
Determinare l'albero dei cammini minimi di radice r = 3 utilizzando
l'algoritmo SPT.S con l'insieme Q realizzato mediante una lista non
ordinata (algoritmo di Dijkstra). Ad ogni iterazione fornire l'insieme
Q all'inizio dell'iterazione, il nodo u selezionato da Q, l'albero
corrente e le relative etichette. Al termine disegnare l'albero ottimo.
Esercizio n. 2.3.2
Dimostrare che se i costi sono non negativi e se si applica la selezione
del nodo di etichetta minima nell'algoritmo SPT, le etichette sono i costi
dei cammini sull'albero corrente e non una loro approssimazione per eccesso.