Shortest Path Problem Flashcards
Definisci lo Shortest Path Problem
Nel Spp bisogna trovare dato un nodo sorgente s il percorso di lunghezza (costo) minimo da s verso tutti gli altri nodi della rete.
Come definiamo la lunghezza dello SP?
La lunghezza del percorso è definita come la somma del costo degli archi che lo compongono
Esplicita la formulazione LP dello SP
Lo Sp ha la seguente formulazione di LP:
Xij= numero di volte in cui l’arco è selezionato nel sp
fun obbiettivo = min Sum {(i,j) in A } xij * cij
vincoli:
outflow - inflow = n-1 se i=s
-1 se i appartiene ad N \ s
Quali sono le assunzioni nello SP?
1) La lunghezza degli archi deve essere intera
2) Deve esistere almeno un percorso da s verso gli altri nodi (almeno una soluzione ammissibile)
3) La rete non contiene cicli con costi negativi
4) La rete è orientanta
Quanto spazio è necessario per memorizzare gli SP?
Sono necessarie n-1 locazioni. Questo perchè un quasliasi Sp da S verso un nodo i, conterrà come sottopercorso sq uno shortest path da s a q.
Quando uno percorso P orientanto da s a K è uno shortest path?
Un percorso P diretto da s a k è uno sp solo e soltanto se d(j)=d(i)+cij qualcunque (i,j) in P
Cosa sono le distance labels?
Le distance label mantengono al loro interno un limite superiore sulla distanza più breve da S.
Quali sono le categorie di algoritmi per lo SP?
Label Setting e Label Correcting, i quali differiscono per come vengono gestite le distance label, nel primo caso ogni label è assegnata come permanente ad ogni step, nel secondo invece le label vengono tenute temporarnee fino al raggiungimento della distanza minima.
Cos’è un ordine topologico?
I nodi di un grafo si definiscono ordinati topologicamente se i nodi sono disposti in modo tale che ogni nodo viene prima di tutti i nodi collegati ai suoi archi uscenti . (i,j) con i
Quando una rete è aciclica?
Quando possiede i nodi ordinati in ordine topologico
Quali algoritmi per l SPP sfruttano l’ordine topologico
Reaching e Pulling method
Algoritmo di Dijsktra
L’algo di dijsktra è un algoritmo LS che può essere adottato su reti senza costi negativi.
Consta di 3 passi:
1) Node selection: si seleziona un nodo temporaneo con distanza minima.
2) Si rende il nodo permanente
3)Distance Update: si aggiornando le distance label dei nodi raggiunti dal nuovo nodo markato
Correttezza di dijkstra
La correttezza del algo di dijstra si basa sul fatto che ad ogni passo selezionamo un nodo etichettato come temporaneo ma che in realtà è gia ottimo.
Condizioni di ottimialità del SPP in LP
La condizione di ottimalità del SPP è equivalente all ‘ammissibilità del problema duale degli SPPs.
Generic Label Correcting Algorithm
Nel generic LC inizializziamo d(s) a 0 tutti le altre label sono temporanee e uguali a infinito. Ad ogni passo si seleziona un nodo per cui d(j) < d(i)+cij, si aggiorna la distance label e si rende permanente. L’algoritmo termina quando nessun nodo viola la condizione di ottimalità. Ha complessità psuedopolinomiale
