PARTE SESTA: Algoritmi su Grafi
-
19/11/02:
-
Il problema dell'albero dei cammini minimi a sorgente singola in
un grafo pesato con pesi non negativi. Definizioni. Tecnica del rilassamento.
-
Algoritmo di Dijkstra.
-
Approfondimento: Esecuzione dell'algoritmo
di Dijkstra.
-
Dispense: 86,
87,
88,
89,
90.
-
20/11/02:
-
Algoritmo di Dijkstra. Dimostrazione di correttezza ed analisi della complessità. Esempi.
-
Dispense:
91,
92,
93.
-
20/11/02:
-
Approfondimento: Esecuzione dell'algoritmo
di Dijkstra con grafo fissato e sorgente variabile. Modifica dell'algoritmo
di Dijkstra per la determinazione del
-
cammino minimo tra un nodo sorgente ed un nodo destinazione.
-
Dispense:
94,
95.
-
21/11/02:
-
Il problema del minimo albero ricoprente di un grafo pesato con
pesi positivi. Definizioni. Teorema dell'appartenenza ad un minimo
-
albero ricoprente di un arco leggero di un taglio. Algoritmo di Kruskal.
Correttezza dell'algoritmo. Esempi.
-
Dispense: 96,
97, 98,
99, 100.
-
28/11/02:
-
Analisi della complessità dell'algoritmo di
Kruskal. Esecuzione dettagliata dell'algoritmo
di Kruskal.
-
Approfondimento: Algoritmo di Prim per il calcolo del minimo albero ricoprente. Confronto con l'algoritmo
di Kruskal.
-
Dispense: 101,
102.