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.

Voci correlate

• Cammino minimo
• Algoritmo di ricerca
• Algoritmo di Dijkstra