Questa voce sull'argomento programmazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia.

L'albero dei cammini minimi di uno specifico vertice ${\displaystyle v}$ di un grafo pesato ${\displaystyle G}$, è un sottografo e un albero i cui vertici sono tutti quelli raggiungibili da ${\displaystyle v}$ in ${\displaystyle G}$ e gli archi sono ridotti in modo che l'unico cammino presente tra ${\displaystyle v}$ e un qualsiasi altro nodo del grafo sia il cammino minimo.

Se il grafo ${\displaystyle 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 ${\displaystyle 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.

• Cammino minimo
• Algoritmo di ricerca
• Algoritmo di Dijkstra

• (EN) Eric W. Weisstein, Albero dei cammini minimi, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica