title: Albero dei cammini minimi
text: # Albero dei cammini minimi
  
  L'albero dei cammini minimi di uno specifico vertice $v$ di un grafo pesato $G$, è un sottografo e un albero i cui vertici sono tutti quelli raggiungibili da $v$ in $G$ e gli archi sono ridotti in modo che l'unico cammino presente tra $v$ e un qualsiasi altro nodo del grafo sia il cammino minimo.
  
  Se il grafo $G$ è connesso l'albero dei cammini minimi è un sottografo ricoprente. L'albero dei cammini minimi ha spesso i nodi etichettati (labelled) con il costo complessivo del cammino minimo per giungere a tale nodo partendo dal nodo radice $v$.
  
  L'albero dei cammini minimi è spesso generato dagli algoritmi di ricerca dei cammini minimi come supporto anche nel caso in cui sia richiesto un solo cammino minimo tra due nodi specifici.
  
  