Estratto del documento

Complessità e correttezza di Print-Shortest-Path

Sia Π = (πij) la matrice dei predecessori di un grafo G di n vertici, dove πij è Nil se i = j o se non esiste un cammino da i a j, altrimenti è il predecessore di j in qualche cammino minimo da i. Data allora la seguente funzione ricorsiva, che stampa un cammino minimo tra due nodi i e j di G:

Print-Shortest-Path

  1. if i == j stampa i
  2. else if πij == Nil stampa "non esiste un cammino da" i "a" j
  3. else Print-Shortest-Path(Π, i, πij) stampa j
  1. Calcolarne la complessità computazionale;
  2. Dimostrarne la correttezza, ovvero che la chiamata Print-Shortest-Path(Π, i, j) stampa correttamente un cammino minimo da i a j, se esiste, o la frase "non esiste un cammino da i a j" in caso contrario.
Anteprima
Vedrai una selezione di 1 pagina su 1
Algoritmi e strutture dati - Esercizi Pag. 1
1 su 1
D/illustrazione/soddisfatti o rimborsati
Acquista con carta o PayPal
Scarica i documenti tutte le volte che vuoi
Dettagli
SSD
Scienze matematiche e informatiche INF/01 Informatica
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher N. A. di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Università degli studi di Napoli Federico II o del prof Sansone Carlo.
Appunti correlati Invia appunti e guadagna

Domande e risposte

Hai bisogno di aiuto?
Chiedi alla community
Vai al forum