Esercitazioni algoritmi RO1

Algoritmi

Ricerca in ampiezza

Basato su FIFO

Ricerca in profondità

Basato su LIFO

Ordinamento topologico

Utile per verificare l'aciclicità

Algoritmi per determinare l'albero dei cammini minimi

• Algoritmo per reti acicliche (se non si associa) O(cm)
• Algoritmo di Dijkstra (se si associa) O(n²)
• Algoritmo di Bellman-Ford (o reti con archi negativi) O(mn)

Algoritmo per determinare il massimo flusso / minimo taglio

• Algoritmo di Ford e Fulkerson (su rete originaria)
• Algoritmo di cammini aumentanti (su rete residuale)

Algoritmo per determinare il minimo albero ricoprente

• Algoritmo di Prim-Dijkstra
• Algoritmo di Kruskal [se ci viene fornita la lista degli archi in ordine crescente]

Condizioni di ottimalità

• n-1 sui bagli fondamentali
• m-(n-1) sui cicli fondamentali

Soluzione del grafo pesato

Per il grafo G = (V, E) pesato sugli spigoli riportato nella seguente figura determinare un albero ricoprente di peso minimo con l'algoritmo di Prim. Certificare l'ottimalità della soluzione.

Tabella dell'algoritmo

Per risolvere l'albero ricoprente, verifichiamo la tabella da destra a sinistra, vedendo il predecessore di ogni vertice selezionato z(T_a^*) = 116

Condizioni di ottimalità

Per le condizioni di ottimalità abbiamo 2 possibilità:

1. Usare la condizione di ottimalità sui tagli: n-1 condizioni
2. Usare la condizione di ottimalità sui cicli: m-(n-1) condizioni

Applichiamo quindi la condizione di ottimalità sui cicli:

• Spigolo (a,b) Cab ≥ u_max (Cae, Cbe) -> 23 ≥ u_max(20,13) OK
• Spigolo (b,c) Cbc ≥ u_max (Cbe, Cc) -> 29 ≥ u_m