mercoledì 26 novembre 2008
Lezione del 25/11/2008
Cammini minimi su grafi con pesi non negativi: Condizione di Dijkstra sulla appartenenza di un arco (u,v) al cammino minimo da s a v; Algoritmo di Dijkstra ed implementazione con heap, correttezza e complessita' computazionale O(|E|log |V|). Esercizio: Un MST di un grafo e' ancora un MST nel caso in cui a tutti gli archi viene sommata la stessa costante? Ed nel caso di un albero dei cammini minimi?
Iscriviti a:
Commenti sul post (Atom)
Nessun commento:
Posta un commento