Cammini minimi

Input:

• grafo direzionato $G=(V,E)$
• per ogni arco $e$, valore $l_e$ (costo, peso o lunghezza dell’arco $e$)
• $s$ = sorgente

Per ogni percorso direzionato $P$, $l(P)$ = somma delle lunghezza degli archi in $P$

<aside> 💡 Problema dei cammini minimi: trova i percorsi direzionati più corti da $s$ verso tutti gli altri nodi

</aside>

Se il grafo non è direzionato possiamo sostituire ogni arco $(u,v)$ con i due archi direzionati $(u,v)$ e $(v,u)$

Cicli negativi

Se esiste un ciclo negativo lungo un percorso da $s$ a $v$, allora non è possibile definire il cammino minimo da $s$ a $v$

Algoritmo di Dijkstra

In $G$ solo archi con lunghezza maggiori o uguali di zero

Algoritmo di Dijkstra:

• ad ogni passo mantiene l’insieme $S$ dei nodi esplorati, cioè di quei nodi $u$ per cui è già stata calcolata la distanza minima $d(u)$ da $s$
• inizializzazione $S=\{s\}$, $d(s)=0$
• ad ogni passo, sceglie tra i nodi non ancora in $S$ ma adiacenti a qualche nodo di $S$, quello che può essere raggiunto nel modo più economico possibile (scelta greedy)
• in altre parole sceglie $v$ che minimizza $d'(v)=min_{e =(u,v): u \in S} d(u)+l_e$, aggiunge $v$ a $S$ e pone $d(v)=d'(v)$
• $d'(v)$ rappresenta la lunghezza del percorso più corto da $s$ a $v$ tra quelli che passano solo per nodi di $S$

Pseudocodice