Cammini minimi

Come si determina il percorso più breve tra nodi di un grafo.

Lunghezza del cammino: numero di archi che lo compongono Percorso più breve: cammino con minor numero di archi

Ci sono vari tipi di cammini:

• da un nodo ad un altro
• da un nodo sorgente a tutti gli altri
• da tutti i nodi a tutti gli altri

Gli archi possono avere dei pesi. La lunghezza in questo caso è la somma dei pesi degli archi che lo compongono.

In questo caso la lunghezza del cammino è 8.

title: Osservazione
Se tutti i pesi sono 1, si torna al caso base.

Input: grafo $G=(V,E)$, funzione di costo non negativa sugli archi $c:E\to R^{+}$, nodo sorgente $s\in V$ Output: albero dei cammini minimi con radice $s$

L’albero dei cammini minimi per un nodo $s$ è un albero di copertura per i nodi raggiungibili da $s$ con radice nel nodo $s$ avente un cammino minimo per ogni nodo raggiungibile da $s$.

I cammini minimi da un nodo a tutti gli altri nodi di un grafo possono sempre essere rappresentati come un albero.

Bisogna stare attenti a come si crea l’albero.

Se L = R allora il cammino minimo lo abbiamo già. Se L > R allora il cammino minimo lo si ha passando per R. Se L < R allora il cammino minimo lo si ha passando per L.

Dal momento che quindi i cammini minimi da un nodo a tutti gli altri si può rappresentare come un albero, l’output del problema deve essere un albero.

asd_31