Albero dei cammini minimi

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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.

Voci correlate[modifica | modifica wikitesto]