Albero dei cammini minimi
Template:S L'albero dei cammini minimi di uno specifico vertice di un grafo pesato , è un sottografo e un albero i cui vertici sono tutti quelli raggiungibili da in e gli archi sono ridotti in modo che l'unico cammino presente tra e un qualsiasi altro nodo del grafo sia il cammino minimo.
Se il grafo è 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 .
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.