Cammino di Peso Minimo

Question 1

Cammino di peso minimo tra due vertici

Answer 1

Dato un grafo G e w: E -> R+ voglio trovare il cammino semplice di peso minimo che collega s a d.

Voglio minimizzare la sommatoria dei pesi degli archi appartenenti al cammino.

Question 2

Algoritmo di forza bruta.

Answer 2

Considero tutti i cammini da s a d e seleziono quello con il peso minimo.

Problema: grande numero di cammini tra s e d da esaminare.

Question 3

Sottocammini di un cammino minimo proprietà

Answer 3

I sottocammini di un cammino minimo sono anch’essi cammini minimi tra i loro vertici finali.

Se il percorso più breve da napoli a milano passa per roma, allora quel percorso include il percorso più breve tra napoli e roma.

PEr trovare il cammino minimo da s a v posso trovare quale vertice u tra gli immediati predecessori di v minimizza il peso del cammino da s a u più l’arco aggiuntivo per arrivare a v.

Question 4

Algoritmo di Dijkstra Ipotesi, Obiettivo e idea generale

Answer 4

Obiettivo: trovare cammino di peso minimo tra il vertice origine e il vertice finale.

Ipo:
- tutti i pesi degli archi sono >= 0 e
- il vertice origine è connesso a tutti gli altri.

Idea:
- g(i) che è il peso del cammino minimo dall’origine s al vertice i
- definisco con L l’insieme dei vertici visitati.

Question 5

Algoritmo di Dijkstra Passaggi

Answer 5

0- Tabella con colonna dei passi, g(i) dei vertici, vertice k scelto e insieme L.

1- Fase di inizializzazione: assegno g(i) a tutti i vertici.
- g(i)=0 se i= vertice iniziale s,
- g(i)=infinito se i!=s.
- Aggiungo a L il vertice iniziale s.

2- Trovo i vertici adiacenti all’insieme L.
Calcolo in quei vertici g(i).
- Aggiungo a L il vertice k per cui g(i) risulta più piccolo tra i vertici non appartenenti a L.

3- Aggiorno g(i) per i vertici adiacenti al vertice k appena aggiunto e aggiungo alla lista L il vertice con g(i) minore.

4- ripeto il passo 3 finché L non coincide con V.