Re: vi offro occasione di dimostrare la vostra cultura sulla teoria dei grafi :-

beccoblu ha scritto:

> ciao a tutti

> la teoria dei grafi l'ho incrociata solo di sfuggita, per cui se scrivo
> cazzate dal punto di vista della terminologia, chiedo venia in anticipo.

> cmq:
>  - il grafo completo (mi pare si dica così: ciascun nodo è connesso
> direttamente a tutti gli altri)
>  - ogni arco ha un suo peso, noto in partenza
>  - mi serve il cammino minimo per la copertura di tutti i nodi

> orbene, che algoritmo si usa? mi dicono "algoritmo di kruskal", ma non
con
> troppa convinzione.

> qualcuno mi sa aiutare?

> d.

Kruskal trova l'albero ricoprente di peso minimo, ossia coprire tutti i
nodi del grafo con gli archi  la cui somma dei pesi è più piccola
possibile. Se devi trovare un cammino minimo da un nodo ad un'altro puoi
usare Dijkstra ,se i pesi degli archi sono tutti positivi,  o Ford
(Shortest-Path) altrimenti. Nota che devi selezionare un nodo sorgente s e
trovi l'albero dei cammini minimi da s a qualsiasi altro nodo. Se la
sorgente cambia devi riapplicare l'algoritmo.







--

questo articolo e` stato inviato via web dal servizio gratuito
http://www.newsland.it/news segnala gli abusi ad abuse@newsland.it

[ Auf dieses Posting antworten ]

Antworten

_kOws (12.05.2008 21:51)