Newsgroup: it.comp.java
Titolo: Algoritmo su una struttura grafo

Devo implementare un algoritmo in java riguardante un cammino minimo e
un grafo.
Vi espongo il problema: supponiamo di avere un grafo del genere
con i nodi : a,b,c,d,e
Composto da i seguenti archi
v1: [a,b]
v2: [b,c]
v3: [c,d]
v4: [b,d]
v5: [a,e]
v6: [e,d]
v7: [e,c]
Ogni arco ha un peso (distanza)
Sto cercando di implementare un algoritmo , che ad esempio dato il
grafo precedente e dato un insieme di nodi (sottografo) , (per esempio
a,b,c,d)  ricavi il cammino che contenga tutti gli elementi del
sottografo e per cui si ha la distanza minima.
Qualcuno ha qualche idea?
Va bene anche  un link di qualche algoritmo anche in inglese, tedesco,
russo pure japponese.Sono verso la disperazione.
Grazie.

Ciao, io sono Alessandro Saitta di 37 anni a Follonica(GR) in via
Cassarello 131 e ti presento Joe Natta: 
www.joenatta.com
 !
Vorresti dialogare con me? Sarà inutile che tu mi spedisca dei
messaggi di posta elettronica (dato che non controllo mai la casella, e
pertanto vado anche in culo a chi me la bombarda pensando di farmi un
dispettone... Altrettanto inutile sarà lasciarmi un messaggio in un
newsgroup/forum, dato che se io dovessi leggere tutti i messaggi dei
newsgroup/forum su cui spammo ci metterei troppo tempo, oltre al fatto
che non mi fotte una sega di leggere le idee altrui in alcun campo)...
Quindi, a parte il fatto che a me del dialogo con gli altri (specie con
quelli che hanno idee  diverse dalle mie) non me ne frega un cazzo
(dato che io non ho bisogno di crescere culturalmente, giacché mi
soddisfa essere ignorante, se ciò significa pensare con la propria
testa), il solo modo è quello di  venirmi ad incontrare di persona.
Però il mio telefono non è inserito in elenco, oltre al fatto che il
mio nome non è presente fra i campanelli di via Cassarello, 131 a
Follonica (GR) (inoltre è anche scollegato, per non farmi rompere il
cazzo neppure per sbaglio... Quando sono in casa, io amo il silenzio
totale), ragion per cui diventerebbe complesso rintracciarmi. Comunque
facendo riferimento ad un luogo che frequento spesso negli ultimi
tempi, esso diventa possibile.
Sarà sufficiente recarsi presso l'Agenzia RAS - Assicurazioni di via
Cassarello 88/90 a Follonica (in orario di ufficio - Sabato e Domenica
esclusi),e chiedere di poter parlare  con Serena (che è la segretaria
personale del Saitta). Successivamente a Serena potrete comunicare che
avete necessità di confrontarvi col Saitta (o solo conoscerlo di
persona nel caso si tratti di ammiratori). Lei dopo aver consultato la
ricca agenda di impegni del Saitta e dopo avergli telefonato (lei
conosce i numeri di telefono dove poterlo rintracciare) sarà
tempestivamente in grado di fissarvi un appuntamento col Saitta in
detta sede (via Cassarello 88/90).
================================================================================================
N.B. Se proseguirai nella lettura ti imbatterai in idee sconclusionate
e senza senso, prive di ogni fondamento logico/culturale e spesso anche
contraddittorie, quindi non perdere tempo ad analizzare le idee del
Saitta o la sua psiche. D'altronde a me piacciono le mie idee e dato
che non obbligo nessuno a condividerle posso pensare cosa cazzo
voglio... Dimenticavo, NON esprimo le mie idee perchè cerco il
confronto e voglio arricchirmi recependo altri punti di vista, io le
esprimo e basta, poi se qualcuno vuole leggerle, bene per lui,
altrimenti non me ne fotte una sega.
================================================================================================
Abbasso la topa, evviva lo spam!
Nel leggere questo mio esordio, la maggior parte della gente penserà
che io sia un finocchio, oppure un frustrato che odia le donne, oppure
un demente in generale... Purtroppo nessuna delle succitate ipotesi
corrisponde alla realtà (tranne forse l'ultima  :).
Spiegherò i concetti fondamentali che mi hanno portato (dal 2003 in
poi) a disinteressarmi in maniera  assoluta del sesso eterosessuale (il
sesso omosessuale non mi ha mai interessato...).
Il fatto che il sesso con le donne non mi interessi, non significa
certo che io odi le donne! Possono arrivare ad essere delle buone
amiche, ma niente di più. Come mai?
Se io evitassi di reprimere i miei istinti animali, sarei
inevitabilmente attratto  dalle donne belle, bone, sexy, trombone
(donne trombone, nel senso che trombano tanto)... Come mai non da una
donna brutta? Se mi attraggono solo le donne belle o attraenti che
siano, escludendo quelle che non lo sono, allora ciò significa che io
sono un opportunista e c'è ben poco di celestiale e/o spirituale
nell'amore passionale. Perciò, dato che le donne brutte, o senza
capelli, o che gli puzza il fiato, o piene di porri sul viso, non mi
piacciono, le escludo tutte a priori (sia belle che brutte) e quando mi
diventa duro, mi faccio una sega (così mi calmo subito :) .
Eppoi oltre a questo lato puramente fisiologico, non piacendomi aver
bisogno degli altri, non mi piacerà neppure sentirmi dipendente da una
donna [finché intrattenevo relazioni più o meno lunghe (max. 3-4
mesi) è sempre successo che  venissi assuefatto da lei,  sia per il
fatto di voler essere sempre accanto a lei, che per il fatto di aver
sempre voglia di trombare, col risultato che quando sei senza compagnia
o non riesci a trombare, ti senti debole ed apatico... Ciò non è
bello..].
Ci si potrebbe domandare allora come mai io riesca a non diventare
dipendente essendo amico-conoscente di una donna: Semplice, perché
quando una non la trombi, non ti ci attacchi (tuttavia esistono anche
quelli che trombano senza attaccarsi, ma io non appartengo a quella
categoria).
In ogni caso, oltretutto, io non appartengo nemmeno alla categoria di
uomini che ha bisogno di una donna all'interno della propria vita, per
ottenere una realizzazione, per crearsi una famiglia (figli, nipoti,
ecc.)... Io non sento il bisogno di completarmi attraverso il
matrimonio... Non mi sento incompleto... Non sento neppure necessità
di avere anche un solo figlio... [Secondo me inoltre, i figli ti fanno
indebolire troppo rendendoti ancora più vulnerabile... La vita se non
è vissuta nel modo giusto, diventa una tortura ed io non voglio certo
star male per lui, se non capisce quale è il modo giusto... Non è
sufficiente che il genitore gli insegni il modo corretto di
affrontarla, il problema sorge perché nella società del cazzo in cui
siamo, lui potrà sempre imparare cazzate dagli altri (pilotati dal
sistema) che gli vorranno  fare il lavaggio del cervello con la scuola,
la cultura, la memoria storica, la tecnologia, il lavoro, il benessere,
le comodità, la moda, la scienza, la medicina, l'informazione, la
politica, ecc...].
Anche in questo caso ci sono  gli uomini che hanno bisogno di una donna
per altri bisogni materiali (oltre a quello fisiologico dello
svuotamento periodico dei coglioni). Tali necessità, possono essere:
lavare (piatti e panni), pulire, preparare da mangiare, condividere
l'affitto (magari alloggiare gratis :), ecc. ... Io non ho da fare
riferimento ad una donna, per le succitate attività, in quanto sono
perfettamente in grado di compierle tutte da me, oltre al fatto che la
casa in cui abito è mia (e ci sto bene da solo senza donne in generale
che rompano la fava. Anche quando viene la mi' mamma o il mi' babbo, io
non vedo l'ora che si tolgano dai coglioni :) .
Quindi, infine io prediligo lo spam alla topa :) .
_________________________________________________________________________________________________
Sapete per quale motivo io spammo?
(Se inizierai a leggere questi miei pensieri, non stendere la tua
recensione personale (per esempio: 'tutte cazzate senza fondamento,
contraddittorie, dettate da un ignorante che non conosce la verità')
senza aver capito il significato intrinseco delle mie affermazioni o
essendo arrivato solo a metà del discorso... Lo dico solo per te,
perché non me ne importa una sega in ogni caso...)
Sono state fatte le più disparate ipotesi sul motivo per cui io mi
diverta a spammare, alimentate anche da miei pensieri che sparavo tanto
per dire due cazzate  relativamente a ciò. Illazioni riguardanti i
miei presunti problemi fisio-psicologici, altre problemi di
egocentrismo che mi portavano a voler essere al centro dell'attenzione
(esibizionismo), ecc.
Adesso però è giunto il momento di dire tutta la verità, solo la
verità, nient'altro che la verità... Il vero motivo, quello per cui
ho iniziato a spammare. è perché la maggior parte delle persone (la
quasi totalità) è attratta dalla Rete, giacché può dire tutto ciò
che vuole senza che nessuno sia in grado di sapere chi sia
(teoricamente, dato che il modo per rintracciare uno che compia in Rete
attività illecite, esiste). I motivi che portano le sopraccitate
persone a nascondersi possono  essere molti. Ci sono quelli che:
- Si vergognano di loro stessi per il loro aspetto fisico, o per
qualcosa di poco dignitoso che hanno compiuto in passato, ma tuttavia
hanno ugualmente il bisogno di relazionarsi con gli altri e di
dialogare (seppur virtualmente) su temi inconcludenti, per esempio
riguardanti altre persone  (Berlusconi è un nano, Bossi è un bavoso,
la Mussolini è Fascista, Bush è un criminale, ecc.) pensando di
accrescere la loro cultura, mentre in realtà riescono solo ad
aumentare la massa di cazzate che hanno  all'interno del cervello
(oltretutto la cultura non serve ad un cazzo nella vita. Serve solo nei
lavori di tipo umanistico, destinati a rimediare gli sbagli degli
altri, ricavandone soldi: avvocati, giudici, medici, ecc, e/o a fare il
lavaggio del carvello  tramite l'istruzione scolastica pilotata dal
sistema (insegnanti, docenti, ecc.) e/o a diffondere le cazzate inutili
alla vita (scienziati, ingegneri, ecc.);
- Sono in grado di apparire come vorrebbero essere nei loro sogni:
belli, forti, impavidi ed invicibili;
- Temono per la propria incolumità, nel far conoscere i propri dati
personali, in quanto potrebbero essere preda di scherzi di cattivo
gusto o vendette in generale;
- Vogliono dialogare sulle loro idee, (solo  gli insicuri hanno queste
voglie, infatti a me non interessa che le mie idee siano lette,
condivise o  meno... Io scrivo, spammo e sono a posto anche se la gente
pensa che io sia un coglione) ma non hanno le palle abbastanza grosse
per parlare a volto scoperto ;
- Trovano soddisfazione nel deridere o contestare qualcuno, pur non
avendo il coraggio (ossia le palle) di dirglielo in faccia,  o magari
proprio perché chi lo vorrebbe deridere o contestare è molto più
ridicolo di quel qualcuno;
In altra analisi, io ho un'idea ben precisa del tipo di uomo (che
chiameremo 'tipo C') a cui da fastidio una persona che attrae
l'attenzione. E' un uomo che vorrebbe farsi notare, ma non ci riesce
quanto vorrebbe, essendo perciò infastidito dal fatto che qualcuno
riesca a mettersi in evidenza, mentre lui non ne è capace. A tal
proposito introduce opinabili regole (netiquette, educazione, 'par
condicio', anti-doping, ecc.) atte a posizionare tutti sullo stesso
piano (cioè uniformare). Oltretutto chi ha detto che chi si fa notare
di più, o chi ha 'di più' sia in effetti avvantaggiato?
Il 'tipo C', non essendo particolarmente dotato intellettivamente,
crede che tutti gli altri individui ragionino in maniera medesima a
lui, perciò dato che lui agisce a seconda di quello che sceglie la
maggioranza, teme che nel caso si spargesse la voce che il rivale è un
grand'uomo, egli (il 'tipo C') possa venirsi a trovare in svantaggio...
Non arriva a ragionare che possano esserci persone capaci di  capire se
una persona vale realmente o no... Non pensa che esistano persone che
non si adeguano alla voce popolare, ma ragionano col proprio cervello.
Io non ho bisogno delle regole, se affronto una competizione... Se il
mio rivale parte avvantaggiato, io non  tento di portarlo al mio stesso
livello... Prima di tutto avere un vantaggio non significa che lui
abbia già la vittoria in tasca, poi se vince e se lo merita, gli
faccio i complimenti, ma se non ne ha merito si sentirà sporco lui
stesso...
[Esempio pratico: Poniamo il caso che io debba affrontare uno
spostamento di 100 m e mi trovi in competizione con Carl Lewis (per chi
non lo sapesse, io pur non essendo paraplegico, non posso correre,
tranne camminare lentamente). Lui con uno sprint di corsa sarà già a
destinazione, mentre io dovrò prendere l'Aixam, ma ci arrivo lo
stesso... Arrivo dopo? In ogni caso a me non cambia niente la vittoria
o meno, e sapete perché? Perché io non ho bisogno degli altri, né
della loro stima e né dei loro soldi... Quindi non mi inmteressa
neppure sapere se lui è 'sotto doping' o se ha qualche vantaggio
rispetto a me. Invece sapete come mai qualcuno si scalda tanto
nell'introdurre regole e norme, nelle competizioni (comprese quelle
elettorali)? Perché egli è un debole/insicuro ha bisogno della stima
e/o del denaro degli altri.
Da tutto ciò ne deriva solo una cosa: IO RIESCO A FAR CONOSCERE
ALESSANDRO SAITTA IN TUTTA LA RETE NAZIONALE (e ci godo), ANDANDO IN
CULO A CHI MI VUOLE MALE [Fabrizio Mindoli di Pisa, Lungarno
Gambacorti, 57 (Il numero di telefono lo ha cambiato. D'altronde era
l'unica cosa che poteva fare... Ha provato anche a denunciarmi alla
Polizia, con l'accusa di diffusione di dati personali, ma non ha
ottenuto niente... Povero stolto) e tutti i brutti dentro e/o criminali
e/o insicuri e/o infami in generale].
Il Saitta: L'UOMO SENZA PUDORE (che odia la privacy, che nella maggior
parte dei casi serve solo a dar voce ai 'senza palle' che vogliono
parlare evitando di farsi scoprire) contro le regole dettate chi vuole
decidere per gli altri (io sono perfettamente in grado di decidere
autonomamente, e faccio cosa cazzo mi pare, dato che non faccio danno a
nessuno) sempre piu' INARRESTABILE ED INVINCIBILE che mai!!! Lo SPAMMER
per antonomasia! E ora nessuno potrà più denunciare un cazzo, perché
uso il 56k :D

 Qualcuno ha qualche idea?
[..]
beh sarebbe utile sapere quanti nodi possono esserci al massimo, se un nodo
o gruppo di nodi puo' essere scollegato dagli altri e se si possiede anche
una collocazione in uno spazio bidimensionale su quale collocare i punti o
se se ne conosce solo la distanza..
-- 
www.iuz-lab.info
Home Politics - 
http://www.iuz-lab.info/homepolitics.php

 sottografo e per cui si ha la distanza minima.
Questo e` un problema classico dell'informatica teorica, e ci sono
tantissimi algortimi per fare quello che ti interessa. Se cerchi su
google "Aberi di copertura minimi" hai gia abbastanza materiale su cui
lavorare. Alcuni nomi sono "algormi di Kruskal e Prim",  "algoritmo di
Dijisktra" . Alcuni di questi pero` pongono condizioni come "grafo
orientato" "sorgente singola", ecc, vedi tu quale algoritmo fa per te!
Un'altra parola chiave per la ricerca su Google e` "Algoritmi e
strutture dati". E` un corso tenuto nelle universita in cui questo
argomento viene affontato. Spesso si trovano delle Slides di qualche
professore che spiegano la cosa. Se hai la possibilita` di andare in
bibblioteca, posso consigliarti due libri interessanti. A) Cormen,
Leisersonl, Rivest: Introduzione agli algortimi (jackson Libri). B)
Sedgewick, Algoritmi in Java (Addison Wesley)

Grazie dei suggerimenti, avevo già dato una occhiata ad esempio
all'algoritmo di Dijisktra
molti algoritmi chiedono però un nodo di partenza ed uno di arrivo, e
queste non sono condizioni che interessano a me, dal nome credo che
forse quello che mi serve è proprio qualche cosa tipo "Alberi di
copertura minimi". In pratica dato quel sottografo (a,b,c,d) ricavare
solo per quello il cammino minimo. Comunque grazie è un inizio,
casomai vi venisse in mente qualche cosa di più specifico io qui leggo
sempre. ciao a tutti.
blackfede ha scritto:


alora io userei l'algoritmo di floyd-warshall.E' un problema di
programmazione dinamica.
l'algoritmo nel tuo caso ha un tempo di calcolo cubico.
non sono altro che 3 for innestati.
prova a guardartelo se non capisci qualcosa dimmelo, che credo che non
sia molto immediato.
con floyd non parti da nessun nodo radice, e trova i cammini minimi fra
tutte le coppie di vertici.
anche io ti consiglio il primo libro sopra citato, io lo ho studiato la
per l'esame di algoritmi sui grafi.solo che della jackson non esite +
in commercio(salvo copie usate).Da quest'anno credo lo produca la
mcgraw-hill.o senno di sicuro lo trovi in inglese come introduction to
algorithms.

Su google giorni fa ho trovato l'algoritmo scritto in java:
prova a cercare dijkstra java ecc...
Mario.

Quello che cerchi si chiama: 
Minimum spanning trees o
Albero ricoprente di peso minimo.
Gli algoritmi piu' noti in letteratura sono quello di 
Kruskal e quello di prim.
Mario.

Grazie davvero a tutti, credo che ci siamo, ho anche trovato
l'algoritmo già implementato.
A chiunque interessasse:
http://www1.cs.columbia.edu/~gskc/Code/AdvancedInternetServices/MinimalSpanningTree/
qui cè il codice java.
Ciaooo