Differenza cammino minimo e minimo albero ricoprente

[Halnow]

Ciao come da oggetto,

qual'è la differenza fra i due?

grazie

[giovanni r.]

On Monday, February 10, 2014 9:56:03 AM UTC+1, Halnow wrote:
> qual'è la differenza fra i due?

dato un grafo il cammino minimo (shortest path) tra due
nodi e' appunto il percorso piu' corto che va da un nodo
all'altro rispetto a qualche tipo di misura.
La piu' ovvia e' il numero degli archi percorsi, ma
se agli archi e' associato un peso, allora si puo' anche
voler determinare il cammino minimo rispetto alla somma
dei pesi. In questo caso il cammino di peso minimo potrebbe
anche non essere il cammino composto dal minimo numero di archi.

il minimo albero ricoprente (meglio noto come minimum spanning tree)
e' un sottografo ad albero del grafo originario tale che
la somma dei pesi degli archi che lo compongono e' il minimo possibile
tra tutti gli alberi che contengono tutti i nodi del grafo.
Siccome un albero che copre n nodi ha sempre n-1 archi, in questo
caso non ha senso minimizzare il numero degli archi...

Comunque queste cose le trovi anche su wikipedia:
http://en.wikipedia.org/wiki/Minimum_spanning_tree
http://en.wikipedia.org/wiki/Shortest_path

(non so se ci sono le pagine in italiano, ma comunque do per scontato
che chi studia informatica conosca almeno l'inglese tecnico necessario
per comprendere queste pagine.)

ciao,
g.
--
http://equal.to/

[Halnow]

giovanni r. <g.r...@iit.cnr.it> ha scritto:

> On Monday, February 10, 2014 9:56:03 AM UTC+1, Halnow wrote:
> > qual'è la differenza fra i due?

Grazie!

Adesso è tutto chiaro :)